題意概述： 有N個人，A,B兩個考場。如果學生i在A考場，總信心值增加xi；如果學生i在B考場，總信心值增加yi。其中還有m對好友，當第i對好友的兩個人都在A考場時，總信心值增加ai；如果兩人都在B考場，總信心值增加bi；如果兩個人在不同考場，那麼總信心值減少ci。 問總信心值最大能達到多少（總... ...
題意概述：
有N個人，A,B兩個考場。如果學生i在A考場，總信心值增加xi；如果學生i在B考場，總信心值增加yi。其中還有m對好友，當第i對好友的兩個人都在A考場時，總信心值增加ai；如果兩人都在B考場，總信心值增加bi；如果兩個人在不同考場，那麼總信心值減少ci。
問總信心值最大能達到多少（總信心值的初始值為0）。
N<=10000,M<=50000,time limit = 1s
分析：
可以很容易發現這是個網路流的問題，但是建模對於不是很熟練的人來說就有點難度了。比如當時考試的時候我有感覺是個最小割但是想不出來怎麼建就去想最大費，但是怎麼建圖發現都是涼的。。。ORZ
最大費是正向的思路，做不出來就反著分析一下。可以發現總信心值的上限一開始是確定的，當一個學生確定在某個考場的時候對這個學生來說就失去了另外一種選擇所可以獲得的收益，即付出了一定代價。最小化代價等價於最大化了收益，於是可以轉化為最小割。考慮到每個人只有兩種狀態，在A考場或者在B考場，那麼就建立源點和匯點分別代表A考場和B考場。然後就開始歡樂連邊。一條邊容量的意義是當這條邊被割掉的時候要付出多少代價。只要真正理解了這種運用最小割的思想實際上這個題也沒什麼難度。（由於有個除以2的問題導致容量變成浮點數所以連邊的時候把所有的代價乘了2）
由於交代起來真的很麻煩就不再贅述了下麵貼出代碼。
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 }
