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计算出至少要通知多少人,至少得花多少电话费就能让所有人都被通知到吗?
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
3 6
把新的图放在belong中
入度为0 cnt++ 再维护每一个强连通分量的最小花费即可
#include<bits/stdc++.h> using namespace std; //input by bxd #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i>=(b);--i) #define RI(n) scanf("%d",&(n)) #define RII(n,m) scanf("%d%d",&n,&m) #define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k) #define RS(s) scanf("%s",s); #define ll long long #define pb push_back #define REP(i,N) for(int i=0;i<(N);i++) #define CLR(A,v) memset(A,v,sizeof A) ////////////////////////////////// #define inf 0x3f3f3f3f const int N=1000+5; int head[3000]; int pos; int minn[N]; struct Edge { int to,nex; }edge[3000]; void add(int a,int b) { edge[++pos].nex=head[a]; head[a]=pos; edge[pos].to=b; } int dfn[N],low[N],Stack[N],vis[N]; int tot=0,index=0; int cnt=0,ans; int cost[N]; int belong[N],in[N]; void tarjan(int x) { dfn[x]=low[x]=++tot; Stack[++index]=x; vis[x]=1; for(int i=head[x];i;i=edge[i].nex) { int v=edge[i].to; if(!dfn[v]) { tarjan(v); low[x]=min(low[x],low[v]); } else if(vis[v]) low[x]=min(low[x],dfn[v]); } if(low[x]==dfn[x]) { cnt++;int v;minn[cnt]=inf; do { v=Stack[index]; minn[cnt]=min(minn[cnt],cost[v]); belong[v]=cnt; vis[v]=0; index--; } while(x!=v); } } int main() { int n,m; while(~RII(n,m)) { CLR(head,0); CLR(dfn,0); CLR(in,0); CLR(vis,0); pos=tot=index=ans=cnt=0; rep(i,1,n)RI(cost[i]); rep(i,1,m) { int a,b;RII(a,b);add(a,b); } rep(i,1,n) if(!dfn[i]) tarjan(i); rep(i,1,n) { int u=belong[i]; for(int j=head[i];j;j=edge[j].nex) { int v=belong[edge[j].to]; if(u!=v) in[v]++; } } int Cnt=0; rep(i,1,cnt) { if(!in[i]) { Cnt++; ans+=minn[i]; } } printf("%d %d ",Cnt,ans); } return 0; }