1 #include 
     
       2 using namespace std; 3 typedef long long ll; 4 inline ll read(){ 5     int x=0,f=1;char ch=getchar(); 6     while(ch>'9'||ch<'0'){
   if(ch=='-')f=-1;ch=getchar();} 7     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 8     return x*f; 9 }10 11 /***********************************************************/12 13 #define inf 0xffffff14 const int N = 510;15 int n,m,ans1,ans2,S,T,idc=1;//偶数开始存，方便异或处理反向边 16 int dis[N],head[N],q[N],from[N];17 bool exi[N];18 19 struct Edge{20     int from, to, next, w, c;21 }ed[100010];22 23 void adde(int u, int v, int w, int c){24     ed[++idc].to = v;25     ed[idc].w = w;26     ed[idc].c = c;27     ed[idc].next = head[u];28     ed[idc].from = u;29     head[u] = idc;30 }31 32 bool spfa(){33     int h=0, t=1, now;34     for(int i=S; i<=T; i++) dis[i] = inf;35     q[0] = S; dis[S] = 0; exi[S] = 1;36     while(h != t){37         now = q[h]; h++; if(h == 500) h = 0;38         for(int k=head[now]; k; k=ed[k].next){39             int v = ed[k].to; 40             if(ed[k].w && ed[k].c + dis[now] < dis[v]){
   //更新距离 41                 dis[v] = dis[now] + ed[k].c;42                 from[v] = k;//末端点属于的边 43                 if( !exi[v] ){44                     exi[v] = 1;45                     q[t++] = ed[k].to;46                     if(t == 500) t = 0;//滚动数组 47                 }48             }49         }50         exi[now] = 0;51     }52     return(dis[T] != inf);53  }54 55 void mcf(){56     int flow = inf;57     int i = from[T];58     while( i ){59         flow = min(flow, ed[i].w);60         i = from[ed[i].from];61     }//沿着路径寻找最大流量 62     ans1++;//多一条路径 63     i = from[T];64     while( i ){65         ans2 += flow * ed[i].c;66         ed[i].w -= flow;67         ed[i^1].w += flow;68         i = from[ed[i].from];69     }//沿着路径统计花费，顺便调整限流 70 }71 72 int main(){73     n = read(); m = read();74     S = 1; T = n+n;75     for(int i = 1;i <= m;i++){76         int u, v, w;77         u = read(); v = read(); w = read();78         adde(u+n, v, 1, w);79         adde(v, u+n, 0, -w);80     }81     //为了限制点流量，往往选择拆点，i为入点，i+n为出点 82     for(int i=2; i