网络流（置顶）

  1 //dinic算法：
  2 #include <stdio.h>
  3 #include <string.h>
  4 #include <math.h>
  5 #include <iostream>
  6 #include <algorithm>
  7 
  8 #define INF 0x3f3f3f3f
  9 using namespace std;
 10 const int maxn = 2010;
 11 const int maxm = 19010;
 12 
 13 int e,S,T;
 14 int first[maxn],next[maxm],work[maxm];
 15 int u[maxm],v[maxm],w[maxm];
 16 
 17 void init(){
 18     e = 0;
 19     memset(first,-1,sizeof(first));
 20 }
 21 
 22 void addedge(int a,int b,int c){
 23     v[e] = b;next[e] = first[a];w[e] = c;first[a] = e++;
 24     v[e] = a;next[e] = first[b];w[e] = 0;first[b] = e++;
 25 }
 26 int d[maxn],q[maxn];
 27 int bfs(){
 28     int rear = 0;
 29     memset(d,-1,sizeof(d));
 30     d[S] = 0;q[rear++] = S;
 31     for(int i = 0;i < rear;i++){
 32         for(int j = first[q[i]];j != -1;j = next[j])
 33             if(w[j] && d[v[j]] == -1){
 34                 d[v[j]] = d[q[i]] + 1;
 35                 q[rear++] = v[j];
 36                 if(v[j] == T)   return 1;
 37             }
 38     }
 39     return 0;
 40 }
 41 
 42 int dfs(int cur,int a){
 43     if(cur == T)    return a;
 44     for(int &i = work[cur];i != -1;i = next[i]){
 45         if(w[i] && d[v[i]] == d[cur] + 1)
 46             if(int t = dfs(v[i],min(a,w[i]))){
 47                 w[i] -= t;w[i^1] += t;
 48                 return t;
 49             }
 50     }
 51     return 0;
 52 }
 53 
 54 int dinic(){
 55     int ans = 0;
 56     while(bfs()){
 57         memcpy(work,first,sizeof(first));
 58         while(int t = dfs(S,INF))   ans += t;
 59     }
 60     return ans;
 61 }
 62 int M,N,CASE;
 63 int ind[maxn],outd[maxn];
 64 int main(){
 65     scanf("%d",&CASE);
 66     while(CASE--)
 67     {
 68         scanf("%d%d",&N,&M);
 69         init();
 70         S=N+1;T=N+2;
 71         memset(ind,0,sizeof(ind));
 72         memset(outd,0,sizeof(outd));
 73         for(int i=1;i<=M;i++){
 74             int x,y,c;
 75             scanf("%d%d%d",&x,&y,&c);
 76             if (c==1) outd[x]++,ind[y]++;
 77             if (c!=1) {
 78                 outd[x]++,ind[y]++;
 79                 addedge(x,y,1);
 80             }
 81         }
 82         bool isok=true;
 83         for(int i=1;i<=N;i++) if ((outd[i]-ind[i])%2!=0) isok=false;
 84         if (!isok) {
 85             printf("impossible\n");
 86             continue;
 87         }
 88         int sum=0;
 89         for(int i=1;i<=N;i++){
 90             int k=(outd[i]-ind[i])/2;
 91             if (k<0) addedge(i,T,-k);
 92             if (k>0) {
 93                 sum+=k;
 94                 addedge(S,i,k);
 95             }
 96         }
 97         int flow=dinic();
 98 ////        cout<<sum<<","<<flow<<endl;
 99         if (flow==sum) printf("possible\n");else printf("impossible\n");
100     }
101     return 0;
102 }