# HDU-1827 Tarjan简单应用
## [HDU-1827](http://acm.hdu.edu.cn/showproblem.php?pid=1827)
## 分析
可以分为 **最小联系人数** + **最小联系花费** 两部分
### 最小联系人数
首先使用Tarjan求强连通分量, 每个分量中只需要通知一个人.
在这个基础上深入思考: 其实任意的一个缩点都可以通知它连接到的其他缩点, 也就是说, **凡是入度不为零的缩点, 都不必通知**.
同时又已知: 一个图中必然有至少一个孤立的强连通分量(缩点入度为0). 因此题目不会无解.
最终结论是**求入度为0的缩点数**
### 最小联系花费
给每个缩点入度为0的强连通分量配一个联系人就完事了.
当然是每个都**枚举出花费最小的**.
## 心得
刚开始觉得还需要用DP或者别的来求最优解, 因为不知道怎么保证最小联系人数下一定有最小联系花费, 万一多联系几个人反而花费得更少呢?
后来发现是本宝宝多虑了:
1. 每一个缩点入度为0的强连通分量都必定需要一个联系人, 不然谁也联系不上里面的人. **从这些分量里各出一个人是必须的**.
2. 在这个基础上再加任何一个人, 都是没有必要的——既不能减少花费(多联系人肯定多花), 也不能联系到更多人(没人需要联系了).
所以**只给孤立分量分配联系人, 就是人数和花费的双最优解**.
## 代码
```cpp
// -------------- GLOBAL ----------------
vector<int> map1[1050]; // 邻接表, 统一从0开始
stack<int> stk1; // 栈
int n, m;
int dfn[1050], low[1050], book[1050]; // dfs序, 最低dfs序, 强连通分量
int dfsClock = 0; // 真实dfs树的遍历顺序
int cnt = 0; // 分量数的累加变量, 注意是从1开始的
int in[1050]; // 入度(注意这里只能判断为0, 多了不靠谱)
int cost[1050]; // 花费
int res[2]; // 结果(最小人数和最小总花费)
// -------------- FUNC ----------------
void tarjan(int k) {
dfn[k] = low[k] = ++dfsClock;
stk1.push(k);
FE(v, map1[k]) {
if (!dfn[v]) {
tarjan(v);
low[k] = min(low[k], low[v]);
} else if (!book[v]) {
low[k] = min(low[k], dfn[v]);
}
}
// 到根了
if (dfn[k] == low[k]) {
++cnt;
while (1) {
int top = stk1.top();
book[top] = cnt;
stk1.pop();
if (top == k)
break;
}
}
}
// -------------- MAIN ----------------
int main() {
while (~scanf("%d%d", &n, &m)) {
dfsClock = cnt = 0;
fill0(dfn);
fill0(book);
fill0(in);
fill0(res);
F0(i, n) {
map1[i].clear();
}
// 输入
F0(i, n) {
scanf("%d", &cost[i]);
}
F0(i, m) {
int u, v;
scanf("%d%d", &u, &v);
map1[--u].push_back(--v);
}
// Tarjan
F0(i, n) {
if (!dfn[i]) {
tarjan(i);
}
}
// 找入度为0的强连通分量
F0(u, n) {
FE(v, map1[u]) {
if (book[u] != book[v]) {
++in[book[v]];
}
}
}
// 找入度为0的强连通分量中花费最小的联系人
F1(i, cnt) {
if (!in[i]) {
int min1 = INF;
F0(j, n) {
if (book[j] == i) {
min1 = min(min1, cost[j]);
}
}
++res[0]; // 联系人个数
res[1] += min1; // 联系人总花费
}
}
printf("%d %d\n", res[0], res[1]);
}
return 0;
}
```
![]()