这题真的坑。。。题意晦涩难懂。出题人你真是够了
题意:有n个城市需要建设道路,有m个公司可以工作。每个公司在开始工作前需要给政府税收,一个公司如果工作了一定必须完成它所负责的那些路段。所花的费用由政府来出。如果X公司建设了a->b路段,Y公司建设了b->c路段。那么我们称X公司和Y公司有单向关系X->Y,规定:如果X工作了,那么和X有关系的公司都要工作。。
求政府最多能赚多少钱。
建图模型:
完成某件事之前必须完成另一件事。这种模型非常经典。
最大权闭合图
在胡伯涛的《最小割模型在信息学竞赛中的应用》中提及。
做法:
u->v
u公司和v公司有直接联系,边权为INF
s->u
如果招标u公司的收益s>0(s=税收-铺设边所花的费用总和),边权为s
v->t
如果招标v公司的收益s<0(s同上),边权为-s
这个模型所求得的最小割(s-t)满足的条件为:
政府的最小花费
所有税收(s>0)之和-最小花费=最大收益
为什么?。割边集只能是简单割边集:s->u或者v->t,不存在u->v。
若s->u是割边,那么代表招标u公司获得的收益<=0
若v->t是割边,那么代表招标v公司获得的收益>=0
代码:
//author: CHC //First Edit Time: 2014-12-04 11:35 //Last Edit Time: 2014-12-04 12:01 #include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <set> #include <vector> #include <map> #include <queue> #include <set> #include <algorithm> #include <limits> using namespace std; typedef long long LL; const int MAXN=1e+4; const int MAXM=1e+5; const int INF = numeric_limits<int>::max(); const LL LL_INF= numeric_limits<LL>::max(); struct Edge { int from,to,ci,next; Edge(){} Edge(int _from,int _to,int _ci,int _next):from(_from),to(_to),ci(_ci),next(_next){} }e[MAXM]; int head[MAXN],tot; int dis[MAXN]; int top,sta[MAXN],cur[MAXN]; inline void init(){ memset(head,-1,sizeof(head)); tot=0; } inline void AddEdge(int u,int v,int ci0,int ci1=0){ e[tot]=Edge(u,v,ci0,head[u]); head[u]=tot++; e[tot]=Edge(v,u,ci1,head[v]); head[v]=tot++; } inline bool bfs(int st,int et){ memset(dis,0,sizeof(dis)); dis[st]=1; queue <int> q; q.push(st); while(!q.empty()){ int now=q.front(); q.pop(); for(int i=head[now];i!=-1;i=e[i].next){ int next=e[i].to; if(e[i].ci&&!dis[next]){ dis[next]=dis[now]+1; if(next==et)return true; q.push(next); } } } return false; } LL Dinic(int st,int et){ LL ans=0; while(bfs(st,et)){ //printf("here\n"); top=0; memcpy(cur,head,sizeof(head)); int u=st,i; while(1){ if(u==et){ int pos,minn=INF; //printf("top:%d\n",top); for(i=0;i<top;i++) { if(minn>e[sta[i]].ci){ minn=e[sta[i]].ci; pos=i; } //printf("%d --> %d\n",e[sta[i]].from,e[sta[i]].to); } for(i=0;i<top;i++){ e[sta[i]].ci-=minn; e[sta[i]^1].ci+=minn; } top=pos; u=e[sta[top]].from; ans+=minn; //printf("minn:%d\n\n",minn); } for(i=cur[u];i!=-1;cur[u]=i=e[i].next) if(e[i].ci&&dis[u]+1==dis[e[i].to])break; if(cur[u]!=-1){ sta[top++]=cur[u]; u=e[cur[u]].to; } else { if(top==0)break; dis[u]=0; u=e[sta[--top]].from; } } } return ans; } struct point { int u,v,t; point(){} point(int _u,int _v,int _t):u(_u),v(_v),t(_t){} }cs[MAXM]; int val[MAXN],tos1; vector <int> vv[MAXN]; int main() { int n,m,k; while(~scanf("%d%d",&n,&m)){ if(n==0&&m==0)continue; init(); tos1=0; for(int i=0;i<MAXN;i++) vv[i].clear(); for(int i=1;i<=m;i++){ scanf("%d",&val[i]); } scanf("%d",&k); for(int i=0,x,y,t,w;i<k;i++){ scanf("%d%d%d%d",&x,&y,&t,&w); cs[tos1++]=point(x,y,t); val[t]-=w; vv[x].push_back(t); } for(int i=0;i<tos1;i++){ for(int j=0;j<(int)vv[cs[i].v].size();j++){ int next=vv[cs[i].v][j]; AddEdge(cs[i].t,next,INF); } } int s=0,t=n+m+1; LL sum=0; for(int i=1;i<=m;i++) { if(val[i]>0)AddEdge(s,i,val[i]),sum+=val[i]; else if(val[i]<0)AddEdge(i,t,-val[i]); } sum-=Dinic(s,t); printf("%I64d\n",sum); } return 0; }