【模拟7.16】通讯（tarjan缩点加拓扑排序）

这题确实水，纯板子，考试意外出错，只拿了暴力分QAQ
tarjan缩点加上拓扑排序，注意这里求最短路径时不能用最小生成树
因为是单向边，不然就可能不是一个联通图了....
  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<string>
  5 #include<cmath>
  6 #include<queue>
  7 #include<stack>
  8 #include<vector>
  9 #include<algorithm>
 10 #define MAXN 100001
 11 #define pt printf("-----------
");
 12 #define push_back ps
 13 #define ll long long 
 14 using namespace std;
 15 int read()
 16 {
 17    int x=0;char c=getchar();
 18    while(c<'0'||c>'9')c=getchar();
 19    while(c<='9'&&c>='0'){x=x*10+c-'0';c=getchar();}
 20    return x;
 21 }
 22 struct node{int to,n,w;}e1[MAXN],e2[MAXN];int head1[MAXN],tot1,head2[MAXN],tot2;
 23 void add1(int u,int v,int w){e1[++tot1].to=v;e1[tot1].w=w;e1[tot1].n=head1[u];head1[u]=tot1;}
 24 void add2(int u,int v,int w){e2[++tot2].to=v;e2[tot2].w=w;e2[tot2].n=head2[u];head2[u]=tot2;}
 25 int low[MAXN],dfn[MAXN];
 26 stack<int>q;
 27 bool vis[MAXN];
 28 int de,cnt=0;
 29 int root=1;
 30 int n,m;
 31 int belong[MAXN];int ru[MAXN];
 32 void tarjan(int x)
 33 { 
 34    low[x]=dfn[x]=++de;
 35    vis[x]=1;q.push(x);
 36    int js=0;
 37    for(int i=head1[x];i;i=e1[i].n)
 38    {
 39       int to=e1[i].to;
 40       if(!dfn[to])
 41       {
 42           tarjan(to);
 43           low[x]=min(low[x],low[to]);
 44       }
 45       else if(vis[to])
 46       { 
 47          low[x]=min(low[x],low[to]);
 48       }
 49    }
 50    if(dfn[x]==low[x])
 51    {
 52        cnt++;
 53        int top=0;
 54        do
 55        {
 56            top=q.top();vis[top]=0;q.pop();belong[top]=cnt;
 57           // printf("top=%d cnt=%d
",top,cnt);
 58        }
 59        while(top!=x);
 60    }
 61 }
 62 void init()
 63 {
 64    for(int x=1;x<=n;++x)
 65    {
 66        for(int i=head1[x];i;i=e1[i].n)
 67        {
 68             int to=e1[i].to;
 69             if(belong[x]==belong[to])continue;
 70             add2(belong[x],belong[to],e1[i].w);
 71             ru[belong[to]]++;
 72             //chu[belong[x]]++;
 73            // printf("belong[%d]=%d-----belong[%d]=%d
",x,belong[x],to,belong[to]);
 74        }
 75    }
 76   /* for(int i=1;i<=n;++i)
 77    {
 78       
 79    }*/
 80 }
 81 queue<int>qq;int f[MAXN];
 82 int biao[MAXN];
 83 int ans=0;
 84 void tuopu(int top)
 85 {
 86     memset(f,0x3f3f3f,sizeof(f));
 87     qq.push(top);
 88     f[top]=0;
 89     while(!qq.empty())
 90     {
 91           int x=qq.front();qq.pop();
 92           for(int i=head2[x];i;i=e2[i].n)
 93           {
 94                int to=e2[i].to;
 95                ru[to]--;
 96                f[to]=min(f[to],e2[i].w);
 97                if(ru[to]==0)
 98                {
 99                    qq.push(to);
100                    ans+=f[to];
101                }
102           }
103     }
104 }
105 void work()
106 {  
107    if(m==n-1)
108    {
109        for(int i=1;i<=m;++i)
110        {
111           int x,y,w;
112           scanf("%d%d%d",&x,&y,&w);
113           ans+=w;
114        }
115        printf("%d
",ans);
116    }
117    else
118    {
119      for(int i=1;i<=m;++i)
120      {
121         int x,y,w;
122         scanf("%d%d%d",&x,&y,&w);
123         x++;y++;
124         //printf("x=%d y=%d
",x,y);
125         add1(x,y,w);
126      } 
127      tarjan(root);
128      init();
129      tuopu(belong[root]);
130      printf("%d
",ans);
131    }
132 }
133 int main()
134 {
135     while(cin>>n>>m)
136     {
137        if(n==0&&m==0)break;
138        memset(low,0,sizeof(low));memset(dfn,0,sizeof(dfn));
139        memset(belong,0,sizeof(belong));memset(ru,0,sizeof(ru));
140        memset(biao,0,sizeof(biao));
141        ans=0;cnt=0;de=0;tot1=0;tot2=0;memset(head1,0,sizeof(head1));memset(head2,0,sizeof(head2));
142        work();
143     }
144 }
View Code