# 【集训试题】exam 信心考 最小割

2018-02-13 10:06:08来源:cnblogs.com作者:KKKorange人点击

N<=10000,M<=50000,time limit = 1s

`  1 #include<iostream>  2 #include<cstdio>  3 #include<cstring>  4 #include<cstdlib>  5 #include<algorithm>  6 #include<cmath>  7 #include<queue>  8 #include<set>  9 #include<map> 10 #include<vector> 11 #include<cctype> 12 #define inf 9e18  13 using namespace std; 14 const int maxn=10005; 15 const int maxm=50005; 16 typedef long long LL; 17  18 int N,M,A[maxn],B[maxn],S,T,tot; 19 struct data{ int u,v,a,b,c; }C[maxm]; 20 struct net_edge{ int from,to,next; LL cap,flow; }NE[4*maxn+10*maxm]; 21 int nfirst[maxn],nnp,cur[maxn],fl[maxn],d[maxn],gap[maxn]; 22 int mq[maxn],front,rear; 23  24 void _scanf(int &x) 25 { 26     x=0; 27     char ch=getchar(); 28     while(ch<'0'||ch>'9') ch=getchar(); 29     while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); 30 } 31 void data_in() 32 { 33     _scanf(N);_scanf(M); 34     for(int i=1;i<=N;i++) _scanf(A[i]); 35     for(int i=1;i<=N;i++) _scanf(B[i]); 36     for(int i=1;i<=M;i++){ 37         _scanf(C[i].u);_scanf(C[i].v); 38         _scanf(C[i].a);_scanf(C[i].b);_scanf(C[i].c); 39     } 40 } 41 void net_add_edge(int u,int v,LL cap) 42 { 43     NE[++nnp]=(net_edge){u,v,nfirst[u],cap,0}; 44     nfirst[u]=nnp; 45     NE[++nnp]=(net_edge){v,u,nfirst[v],0,0}; 46     nfirst[v]=nnp; 47 } 48 void _net_add_edge(int u,int v,LL cap) 49 { 50     NE[++nnp]=(net_edge){u,v,nfirst[u],cap,0}; 51     nfirst[u]=nnp; 52     NE[++nnp]=(net_edge){v,u,nfirst[v],cap,0}; 53     nfirst[v]=nnp; 54 } 55 void build_net() 56 { 57     S=N+1,T=N+2,tot=T; 58     for(int i=1;i<=N;i++){ 59         net_add_edge(S,i,(LL)2*B[i]); 60         net_add_edge(i,T,(LL)2*A[i]); 61     } 62     int u,v; 63     for(int i=1;i<=M;i++){ 64         u=C[i].u,v=C[i].v; 65         net_add_edge(S,u,(LL)C[i].b+C[i].c); 66         net_add_edge(u,T,(LL)C[i].a+C[i].c); 67         net_add_edge(S,v,(LL)C[i].b+C[i].c); 68         net_add_edge(v,T,(LL)C[i].a+C[i].c); 69         _net_add_edge(u,v,(LL)C[i].a+C[i].b+(LL)2*C[i].c); 70     } 71 } 72 void BFS(int s) 73 { 74     for(int i=1;i<=tot;i++) d[i]=tot; 75     front=rear=0; 76     mq[rear++]=s; 77     d[s]=0; 78     int i,j; 79     while(front!=rear){ 80         i=mq[front++]; 81         for(int p=nfirst[i];p;p=NE[p].next){ 82             j=NE[p].to; 83             if(d[j]==tot) d[j]=d[i]+1,mq[rear++]=j; 84         } 85     } 86 } 87 LL augment(int s,int t) 88 { 89     int now=t; LL flow=inf; 90     while(now!=s){ 91         flow=min(flow,NE[fl[now]].cap-NE[fl[now]].flow); 92         now=NE[fl[now]].from; 93     } 94     now=t; 95     while(now!=s){ 96         NE[fl[now]].flow+=flow,NE[(fl[now]-1^1)+1].flow-=flow; 97         now=NE[fl[now]].from; 98     } 99     return flow;100 }101 LL ISAP(int s,int t)102 {103     memcpy(cur,nfirst,sizeof(cur));104     BFS(t);105     for(int i=1;i<=tot;i++) gap[d[i]]++;106     LL maxflow=0; int now=s,j;107     while(d[s]<tot){108         if(now==t){109             maxflow+=augment(s,t);110             now=s;111         }112         bool ok=0;113         for(int p=cur[now];p;p=NE[p].next){114             j=NE[p].to;115             if(d[j]+1==d[now]&&NE[p].cap>NE[p].flow){116                 ok=1;117                 cur[now]=fl[j]=p;118                 now=j;119                 break;120             }121         }122         if(!ok){123             int minl=tot;124             for(int p=nfirst[now];p;p=NE[p].next){125                 j=NE[p].to;126                 if(d[j]+1<minl&&NE[p].cap>NE[p].flow) minl=d[j]+1;127             }128             if(--gap[d[now]]==0) break;129             gap[d[now]=minl]++;130             cur[now]=nfirst[now];131             if(now!=s) now=NE[fl[now]].from;132         }133     }134     return maxflow;135 }136 void work()137 {138     build_net();139     LL sum=0;140     for(int i=1;i<=N;i++) sum+=A[i],sum+=B[i];141     for(int i=1;i<=M;i++)142         sum+=C[i].a,sum+=C[i].b,sum+=C[i].c;143     cout<<sum-ISAP(S,T)/2<<'/n';144 }145 int main()146 {147     data_in();148     work();149     return 0;150 }`