Barricade

  1 //  2 //by coolxxx  3 //#include<bits/stdc++.h>  4 #include<iostream>  5 #include<algorithm>  6 #include<string>  7 #include<iomanip>  8 #include<map>  9 #include<stack> 10 #include<queue> 11 #include<set> 12 #include<bitset> 13 #include<memory.h> 14 #include<time.h> 15 #include<stdio.h> 16 #include<stdlib.h> 17 #include<string.h> 18 //#include<stdbool.h> 19 #include<math.h> 20 #define min(a,b) ((a)<(b)?(a):(b)) 21 #define max(a,b) ((a)>(b)?(a):(b)) 22 #define abs(a) ((a)>0?(a):(-(a))) 23 #define lowbit(a) (a&(-a)) 24 #define sqr(a) ((a)*(a)) 25 #define swap(a,b) ((a)^=(b),(b)^=(a),(a)^=(b)) 26 #define mem(a,b) memset(a,b,sizeof(a)) 27 #define eps (1e-10) 28 #define J 10000 29 #define mod 1000000007 30 #define MAX 0x7f7f7f7f 31 #define PI 3.14159265358979323 32 #pragma comment(linker,"/STACK:1024000000,1024000000") 33 #define N 1004 34 #define M 10004 35 using namespace std; 36 typedef long long LL; 37 double anss; 38 LL aans; 39 int cas,cass; 40 int n,m,lll,ans; 41 int nn,S,T; 42 int d[N],vd[N],last[N],last1[N]; 43 bool u[N]; 44 struct xxx 45 { 46     int next,to,q; 47 }a[M<<1],b[M<<1]; 48 void add(int x,int y,int z) 49 { 50     a[++lll].next=last[x]; 51     a[lll].to=y; 52     a[lll].q=z; 53     last[x]=lll; 54 } 55 void link(int x,int y,int z) 56 { 57     b[++cas].next=last1[x]; 58     b[cas].to=y; 59     b[cas].q=z; 60     last1[x]=cas; 61 } 62 int sap(int u,int f) 63 { 64     int i,v,tt,asp=0,mix=nn-1; 65     if(u==T)return f; 66     for(i=last[u];i;i=a[i].next) 67     { 68         v=a[i].to; 69         if(a[i].q>0) 70         { 71             if(d[u]==d[v]+1) 72             { 73                 tt=sap(v,min(f-asp,a[i].q)); 74                 asp+=tt; 75                 a[i].q-=tt; 76                 a[i^1].q+=tt; 77                 if(asp==f || d[S]==nn) 78                     return asp; 79             } 80             mix=min(mix,d[v]); 81         } 82     } 83     if(asp!=0)return asp; 84     if(!--vd[d[u]])d[S]=nn; 85     else vd[d[u]=mix+1]++; 86     return asp; 87 } 88 void bfs() 89 { 90     int now,to,i; 91     queue<int>q; 92     mem(d,MAX); 93     u[n]=1;q.push(n);d[n]=0; 94     while(!q.empty()) 95     { 96         now=q.front();q.pop(); 97         if(d[now]>=d[S])continue; 98         for(i=last1[now];i;i=b[i].next) 99         {100             to=b[i].to;101             if(d[now]+1>d[to])continue;102             d[to]=d[now]+1;103             add(now,to,0),add(to,now,b[i].q);104             if(!u[to])105             {106                 u[to]=1;107                 if(to!=S)q.push(to);108             }109         }110     }111     mem(d,0);112 }113 int main()114 {115     #ifndef ONLINE_JUDGEW116     freopen("1.txt","r",stdin);117 //    freopen("2.txt","w",stdout);118     #endif119     int i,j,k;120     int x,y,z,f;121 //    init();122     for(scanf("%d",&cass);cass;cass--)123 //    for(scanf("%d",&cas),cass=1;cass<=cas;cass++)124 //    while(~scanf("%s",s))125 //    while(~scanf("%d",&n))126     {127         lll=cas=1;ans=0;128         mem(u,0);mem(vd,0);mem(last,0);mem(last1,0);129         scanf("%d%d",&n,&m);130         for(i=1;i<=m;i++)131         {132             scanf("%d%d%d",&x,&y,&z);133             link(x,y,z),link(y,x,z);134         }135         nn=n;136         S=1,T=n;137         vd[0]=nn;138         bfs();139         while(d[S]<nn)140         {141             f=sap(S,MAX);142             ans+=f;143         }144         printf("%d\n",ans);145     }146     return 0;147 }148 /*149 //150 151 //152 */