Summer Holiday
Time Limit: 10000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2088 Accepted Submission(s): 966
Problem Description
To see a World in a Grain of Sand
And a Heaven in a Wild Flower,
Hold Infinity in the palm of your hand
And Eternity in an hour.
—— William Blake
听说lcy帮大家预定了新马泰7日游，Wiskey真是高兴的夜不能寐啊，他想着得快点把这消息告诉大家，虽然他手上有所有人的联系方式，但是一个一个联系过去实在太耗时间和电话费了。他知道其他人也有一些别人的联系方式，这样他可以通知其他人，再让其他人帮忙通知一下别人。你能帮Wiskey计算出至少要通知多少人，至少得花多少电话费就能让所有人都被通知到吗？
Input
多组测试数组，以EOF结束。
第一行两个整数N和M（1<=N<=1000, 1<=M<=2000），表示人数和联系对数。
接下一行有N个整数，表示Wiskey联系第i个人的电话费用。
接着有M行，每行有两个整数X，Y，表示X能联系到Y，但是不表示Y也能联系X。
Output
输出最小联系人数和最小花费。
每个CASE输出答案一行。
Sample Input
12 16
2 2 2 2 2 2 2 2 2 2 2 2
1 3
3 2
2 1
3 4
2 4
3 5
5 4
4 6
6 4
7 4
7 12
7 8
8 7
8 9
10 9
11 10
Sample Output
哈哈，一遍ac。
思路：求出图中所有SCC，再进行缩点，缩点的同时求出SCC的入度。
一：若入度为0，说明该SCC不可以由其它SCC间接连通，此时对于该SCC需要被直接连通，求出连通该SCC的最少花费，人数加一；
二：若入度不为0，说明该SCC可以由其它入度为0的SCC来间接连通自己，所以不需要花费。
AC代码：
#include <cstdio>
#include <cstring>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#define MAXN 1000+10
#define MAXM 4000+10
#define INF 1000000
using namespace std;
struct Edge
{
int from, to, next;
}edge[MAXM];
int head[MAXN], edgenum;
vector<int> G[MAXN];//存储新图
vector<int> scc[MAXN];//存储SCC里面的点
int low[MAXN], dfn[MAXN];
int dfs_clock;
int sccno[MAXN], scc_cnt;//sccno[i]表示i属于哪个SCC scc_cnt是SCC计数器
stack<int> S;
bool Instack[MAXN];//标记是否进栈
int n, m;
int cost[MAXN];//给某人打电话的花费
int in[MAXN];//记录SCC的入度
void init()
{
edgenum = 0;
memset(head, -1, sizeof(head));
}
void addEdge(int u, int v)
{
Edge E = {u, v, head[u]};
edge[edgenum] = E;
head[u] = edgenum++;
}
void getMap()
{
int a, b;
for(int i = 1; i <= n; i++)
scanf("%d", &cost[i]);
while(m--)
{
scanf("%d%d", &a, &b);
addEdge(a, b);
}
}
void tarjan(int u, int fa)
{
int v;
low[u] = dfn[u] = ++dfs_clock;
S.push(u);
Instack[u] = true;
for(int i = head[u]; i != -1; i = edge[i].next)
{
v = edge[i].to;
if(!dfn[v])
{
tarjan(v, u);
low[u] = min(low[u], low[v]);
}
else if(Instack[v])
low[u] = min(low[u], dfn[v]);
}
if(low[u] == dfn[u])
{
scc_cnt++;//SCC数目加一
scc[scc_cnt].clear();
for(;;)
{
v = S.top(); S.pop();
sccno[v] = scc_cnt;
Instack[v] = false;
scc[scc_cnt].push_back(v);//存储SCC里面的点
if(v == u) break;
}
}
}
void find_cut(int l, int r)
{
memset(low, 0, sizeof(low));
memset(dfn, 0, sizeof(dfn));
memset(sccno, 0, sizeof(sccno));
memset(Instack, false, sizeof(Instack));
dfs_clock = scc_cnt = 0;
for(int i = l; i <= r; i++)
if(!dfn[i]) tarjan(i, -1);
}
void suodian()//缩点
{
for(int i = 1; i <= scc_cnt; i++) G[i].clear(), in[i] = 0;
for(int i = 0; i < edgenum; i++)
{
int u = sccno[edge[i].from];
int v = sccno[edge[i].to];
if(u != v)
G[u].push_back(v), in[v]++;
}
}
void solve()
{
if(scc_cnt == 1)//只有一个SCC
{
sort(cost+1, cost+n+1);
printf("%d %d\n", 1, cost[1]);
}
else
{
int ans = 0;//通知人数
int mincost = 0;//最少花费
for(int i = 1; i <= scc_cnt; i++)//求解每个SCC
{
if(in[i])//入度不为0
continue;
ans++;
int each = INF;//对于入度为0的SCC 求解
for(int j = 0; j < scc[i].size(); j++)//遍历当前SCC里面所有点
each = min(cost[scc[i][j]], each);
mincost += each;
}
printf("%d %d\n", ans, mincost);
}
}
int main()
{
while(scanf("%d%d", &n, &m) != EOF)
{
init();
getMap();
find_cut(1, n);
suodian();
solve();
}
return 0;
}
| 
转播
