中文题一道,好题啊,读题简单多了,做起来也不难,就是缩点,缩点完成后,入度为0的点 就是需要主人公特意需要去打电话的点,缩点后 对于某一个团的最小话费就很好求了,直接暴力查找就可以了,
#include<iostream> #include<cstdio> #include<list> #include<algorithm> #include<cstring> #include<string> #include<queue> #include<stack> #include<map> #include<vector> #include<cmath> #include<memory.h> #include<set> #define ll long long #define eps 1e-7 #define inf 0xfffffff const ll INF = 1ll<<61; using namespace std; //vector<pair<int,int> > G; //typedef pair<int,int > P; //vector<pair<int,int> > ::iterator iter; // //map<ll,int >mp; //map<ll,int >::iterator p; // typedef struct Node { int from,to; int nex; }; Node edge[1000 * 10]; int head[2000 + 10],Stack[2000 + 10],low[2000 + 10],dfn[2000 + 10],id[2000 + 10],w[1000 + 10]; bool vis[2000 + 10]; int tot,vis_num,stack_num,scc_num; void clear() { memset(head,-1,sizeof(head)); memset(Stack,0,sizeof(Stack)); memset(low,0,sizeof(low)); memset(dfn,-1,sizeof(dfn)); memset(id,0,sizeof(id)); memset(vis,false,sizeof(vis)); memset(w,0,sizeof(w)); memset(edge,0,sizeof(edge)); tot = 0; vis_num = 0; stack_num = 0; scc_num = 0; } void addedge(int u,int v) { edge[tot].from = u; edge[tot].to = v; edge[tot].nex = head[u]; head[u] = tot++; } void tarjan(int v) { dfn[v] = low[v] = ++vis_num; vis[v] = true; Stack[stack_num++] = v; for(int i=head[v];i!=-1;i=edge[i].nex) { int u = edge[i].to; if(dfn[u] == -1) { tarjan(u); low[v] = min(low[u],low[v]); } else if(vis[u]) low[v] = min(low[v],dfn[u]); } int tmp; if(low[v] == dfn[v]) { scc_num++; do { tmp = Stack[--stack_num]; id[tmp] = scc_num; vis[tmp] = false; }while(tmp != v); } } void cal(int n) { for(int i=1;i<=n;i++) if(dfn[i] == -1) tarjan(i); } int main() { int n,m; while(scanf("%d %d",&n,&m) == 2) { clear(); for(int i=1;i<=n;i++) scanf("%d",&w[i]); int a,b; while(m--) { scanf("%d %d",&a,&b); addedge(a,b); } cal(n); int in[2000 + 10];//入度 int hehe[2000 + 10];//话费 memset(in,0,sizeof(in)); for(int i=0;i<tot;i++) { int u = edge[i].from,v = edge[i].to; if(id[u] != id[v]) in[ id[v] ]++; } int ans1 = 0; for(int i=1;i<=scc_num;i++) { if(in[i] == 0) ans1++; hehe[i] = inf; } for(int i=1;i<=n;i++) { int tmp = id[i]; if(in[tmp] == 0) hehe[tmp] = min(hehe[tmp],w[i]); } int ans2 = 0; for(int i=1;i<=scc_num;i++) if(hehe[i] != inf) ans2 += hehe[i]; printf("%d %d\n",ans1,ans2); } return EXIT_SUCCESS; }