题意：有N个城市，M个公司。现在需要建立交通是获得的利益最大。如果2个公司A,B, A修的路为Xa->Ya,B的路为Xb->Yb,如果Ya==Xb，那么这2个公司有关系。
对于每个公司都有获得的税，和需要付出的价值。求最大能够得到的利润为多少。
分析：
很明显是最小权闭合图。最大获利=总共的值-（付出的值+没得到的值）。
#include<stdio.h> #include<string.h> #include<queue> #define INF 99999999 using namespace std; const int maxn = 6500; struct node { int to; int v; int flag; int next; }edge[maxn*maxn/2]; struct company { int x; int y; int t; int z; }temp[3100]; int index,pre[maxn],S,T,vis[maxn]; int val[5050],fv[5050]; int min(int x,int y){return x<y?x:y;} void add(int x,int y,int z) { edge[index].to=y; edge[index].v=z; edge[index].flag=index+1; edge[index].next=pre[x]; pre[x]=index++; edge[index].to=x; edge[index].v=0; edge[index].flag=index-1; edge[index].next=pre[y]; pre[y]=index++; } int dfs(int u,int low) { int i,used=0; if(u==T) return low; for(i=pre[u];i!=-1&&used<low;i=edge[i].next) { if(edge[i].v>0&&vis[edge[i].to]==vis[u]+1) { int a=dfs(edge[i].to,min(edge[i].v,low-used)); edge[i].v-=a; edge[edge[i].flag].v+=a; used+=a; } } if(!used) vis[u]=-1; return used; } bool BFS() { int i; queue<int>q; memset(vis,-1,sizeof(vis)); vis[0]=1; q.push(0); while(!q.empty()) { int t=q.front(); q.pop(); for(i=pre[t];i!=-1;i=edge[i].next) { if(edge[i].v&&vis[edge[i].to]<0) { vis[edge[i].to]=vis[t]+1; q.push(edge[i].to); } } } if(vis[T]>0) return true; return false; } int main() { int n,m,i,j,k; while(~scanf("%d%d",&n,&m)) { if(!n&&!m) break; int sum=0; index=1; memset(pre,-1,sizeof(pre)); memset(fv,0,sizeof(fv)); for(i=1;i<=m;i++) { scanf("%d",&val[i]); } scanf("%d",&k); for(i=1;i<=k;i++) { scanf("%d%d%d%d",&temp[i].x,&temp[i].y,&temp[i].t,&temp[i].z); val[temp[i].t]-=temp[i].z; } for(i=1;i<=m;i++) { if(val[i]<0) add(i,m+1,-val[i]); else { sum+=val[i]; add(0,i,val[i]); } } for(i=1;i<=k;i++) { for(j=1;j<=k;j++) { if(i==j)continue; if(temp[i].y==temp[j].x) { if(temp[i].t!=temp[j].t) { add(temp[i].t,temp[j].t,INF); } } } } int ans=0; S=0,T=m+1; while(BFS()) { int a=dfs(0,INF); if(!a)break; ans+=a; } printf("%d ",sum-ans); } }