本文主要是介绍hdu 3917 Road constructions，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：有m个公司，k条路，每个公司修条路都要向政府交一定的税，同时政府也要向该公司付修路费，还有如果a和b公司是合作关
系，那么你选了a修路，就必须要选b。（如果a负责修A-B,b负责修B-C，那么就定义a和b为合作的关系），问政府最大收益为多少。
最大权闭合图:
建立超级源点和每个公司相连，权值为该公司修路的税费。
每个公司和其合作的公司相连，权值为inf。
每个公司和汇点相连，权值为它对应的修路费。
跑一遍sap（），
税费总和-sap（）即为答案。
#include<stdio.h>
#include<string.h>
#include<iostream>
#define N 40010
#define inf 100000000
using namespace std;
struct Edge{
int u,v,c,next;
}edge[N];
int head[N],pre[N],cur[N],dis[N],gap[N],a[N],b[N],company[N],c[N],s[N];
int n,m,e,num,k,sum,start,end;
void add_adge(int u,int v,int c)
{
edge[e].u=u; edge[e].v=v; edge[e].c=c; edge[e].next=head[u]; head[u]=e++;
edge[e].u=v; edge[e].v=u; edge[e].c=0; edge[e].next=head[v]; head[v]=e++;
}
int sap()
{
int flow=0,aug=inf,u;
bool flag;
for(int i=0;i<=m+1;i++)
{
cur[i]=head[i];
gap[i]=dis[i]=0;
}
gap[0]=m+2;
u=pre[start]=start;
while(dis[start]<m+2)
{
flag=0;
for(int &j=cur[u];j!=-1;j=edge[j].next)
{
int v=edge[j].v;
if(edge[j].c>0&&dis[u]==dis[v]+1)
{
flag=1;
if(edge[j].c<aug) aug=edge[j].c;
pre[v]=u;
u=v;
if(u==end)
{
flow+=aug;
while(u!=start)
{
u=pre[u];
edge[cur[u]].c-=aug;
edge[cur[u]^1].c+=aug;
}
aug=inf;
}
break;
}
}
if(flag) continue;
int mindis=m+2;
for(int j=head[u];j!=-1;j=edge[j].next)
{
int v=edge[j].v;
if(edge[j].c>0&&dis[v]<mindis)
{
mindis=dis[v];
cur[u]=j;
}
}
if((--gap[dis[u]])==0) break;
gap[dis[u]=mindis+1]++;
u=pre[u];
}
return flow;
}
int main()
{
while(scanf("%d%d",&n,&m)&&n&&m)
{
int i,j;
if(n>m) end=n+1;
else end=m+1;
e=sum=start=0;
memset(head,-1,sizeof(head));
memset(s,0,sizeof(s));
for(i=1;i<=m;i++)
{
scanf("%d",&num);
add_adge(0,i,num);
sum+=num;
}
scanf("%d",&k);
for(i=1;i<=k;i++)
{
scanf("%d%d%d%d",&a[i],&b[i],&company[i],&c[i]);
s[company[i]]+=c[i];
}
for(i=1;i<=k;i++)
for(j=1;j<=k;j++)
{
if(a[j]==b[i]&&company[i]!=company[j])
add_adge(company[i],company[j],inf);
}
for(i=1;i<=m;i++)
{
add_adge(i,end,s[i]);
}
printf("%d\n",sum-sap());
}
return 0;
}
这篇关于hdu 3917 Road constructions的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
