n个村庄m条带权路，权值为花费，村庄可以造东西卖东西，造完东西可以换地方卖，给出每个村庄造东西花费a和最多个数b、卖东西价值c和最多个数d，求最大收益。
裸的费用流。然而还WA了一发。很好。
建源向每个村庄连边(b,a)，(b,a)表示容量b费用a，每个村庄向汇点连边(d,-c)，村庄间有路就互相连边(inf,v)，v为边权，然后就是最小费用流。
不是最小费用最大流！！把费用最大流SPFA中最后一句判断改成<0即可，因为>=0时的费用可以不要他。
1 #include<stdio.h> 2 #include<stdlib.h> 3 #include<string.h> 4 #include<algorithm> 5 #include<math.h> 6 #include<iostream> 7 using namespace std; 8 9 int n,m,s,t; 10 #define maxn 10011 11 #define maxm 50011 12 struct Edge{int from,to,next,cap,flow,cost;}; 13 const int inf=0x3f3f3f3f; 14 struct Graph 15 { 16 Edge edge[maxm]; 17 int n,first[maxn],d[maxn],cur[maxn],le,cost,s,t; 18 bool inq[maxn],mark[maxn]; 19 void clear() {memset(first,0,sizeof(first));le=2;cost=0;} 20 void in(int x,int y,int cap,int cost) 21 { 22 Edge& e=edge[le]; 23 e.from=x;e.to=y;e.cap=cap;e.flow=0; 24 e.cost=cost;e.next=first[x];first[x]=le++; 25 } 26 void insert(int x,int y,int cap,int cost) 27 { 28 in(x,y,cap,cost); 29 in(y,x,0,-cost); 30 } 31 bool SPFA() 32 { 33 memset(d,0x3f,4*(n+1)); 34 int que[233333],head=0,tail=1; 35 que[0]=s;inq[s]=1;d[s]=0; 36 while (head<tail) 37 { 38 const int now=que[head++]; 39 if (head==233333) head=0; 40 inq[now]=0; 41 for (int i=first[now];i;i=edge[i].next) 42 { 43 Edge& e=edge[i]; 44 if (e.cap>e.flow && d[e.to]>d[now]+e.cost) 45 { 46 d[e.to]=d[now]+e.cost; 47 if (!inq[e.to]) 48 { 49 que[tail++]=e.to; 50 inq[e.to]=1; 51 if (tail==233333) tail=0; 52 } 53 } 54 } 55 } 56 return d[t]<0; 57 } 58 int dfs(int x,int a) 59 { 60 if (x==t || !a) {cost+=a*d[t];return a;} 61 mark[x]=1; 62 int flow=0,f; 63 for (int& i=cur[x];i;i=edge[i].next) 64 { 65 Edge& e=edge[i]; 66 if (!mark[e.to] && d[e.to]==d[x]+e.cost && (f=dfs(e.to,min(a,e.cap-e.flow)))>0) 67 { 68 flow+=f; 69 e.flow+=f; 70 edge[i^1].flow-=f; 71 a-=f; 72 if (!a) break; 73 } 74 } 75 // mark[x]=0; 76 return flow; 77 } 78 int MCMF(int s,int t) 79 { 80 this->s=s;this->t=t; 81 int flow=0;cost=0; 82 memset(mark,0,sizeof(mark)); 83 memset(inq,0,sizeof(inq)); 84 while (SPFA()) 85 { 86 memset(mark,0,n+1); 87 for (int i=1;i<=n;i++) cur[i]=first[i]; 88 flow+=dfs(s,inf); 89 } 90 return cost; 91 } 92 }g; 93 int a,b,c,d; 94 int main() 95 { 96 while (scanf("%d%d",&n,&m)==2) 97 { 98 g.clear();g.n=n+2;s=n+1;t=s+1; 99 for (int i=1;i<=n;i++) 100 { 101 scanf("%d%d%d%d",&a,&b,&c,&d); 102 g.insert(s,i,b,a); 103 g.insert(i,t,d,-c); 104 } 105 for (int i=1;i<=m;i++) 106 { 107 scanf("%d%d%d",&a,&b,&c); 108 if (a==b) continue; 109 g.insert(a,b,inf,c); 110 g.insert(b,a,inf,c); 111 } 112 printf("%d ",-g.MCMF(s,t)); 113 } 114 return 0; 115 }