4 2 500 10 4 1 2 1 10 2 3 1 20 4 3 1 30 1 4 2 60 4 2 500 100 5 1 2 1 10 2 3 1 20 4 3 1 30 4 3 2 10 1 4 2 60 3 1 10 3 1 2 1 100 2 3 1 100 3 1 1 100 0 0
440 470 0Hintfor second test case, if you choose company 2 responsible ways, then you must choose the path of responsible company 1, but if you choose company 1, then you do not have to choose company 2.
思路：做最大权闭合图的题就是要找到有相互依赖关系的两个集合。题目中告诉了公司之间有依赖关系，那么就以公司为节点，源点和每个公司连边权为纳税，公司和会点连边权为花费，公司与公司之间有联系的连边权为INF。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
#include <stack>
#include <vector>
#include <set>
#include <queue>
#pragma comment (linker,"/STACK:102400000,102400000")
#define maxn 1005
#define MAXN 5005
#define mod 1000000009
#define INF 0x3f3f3f3f
#define pi acos(-1.0)
#define eps 1e-6
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define FRE(i,a,b) for(i = a; i <= b; i++)
#define FRL(i,a,b) for(i = a; i < b; i++)
#define mem(t, v) memset ((t) , v, sizeof(t))
#define sf(n) scanf("%d", &n)
#define sff(a,b) scanf("%d %d", &a, &b)
#define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)
#define pf printf
#define DBG pf("Hi\n")
const int MAXM = 200010;
typedef long long ll;
using namespace std;
struct Edge
{
int to,next,cap,flow;
}edge[MAXM];
int tol;
int head[MAXN];
int gap[MAXN],dep[MAXN],pre[MAXN],cur[MAXN];
void init()
{
tol=0;
memset(head,-1,sizeof(head));
}
//加边，单向图三个参数，双向图四个参数
void addedge(int u,int v,int w,int rw=0)
{
edge[tol].to=v; edge[tol].cap=w; edge[tol].next=head[u];
edge[tol].flow=0; head[u]=tol++;
edge[tol].to=u; edge[tol].cap=rw; edge[tol].next=head[v];
edge[tol].flow=0; head[v]=tol++;
}
//输入参数：起点，终点，点的总数
//点的编号没有影响，只要输入点的总数
int sap(int start,int end,int N)
{
memset(gap,0,sizeof(gap));
memset(dep,0,sizeof(dep));
memcpy(cur,head,sizeof(head));
int u=start;
pre[u]=-1;
gap[0]=N;
int ans=0;
while (dep[start]<N)
{
if (u==end)
{
int Min=INF;
for (int i=pre[u];i!=-1;i=pre[edge[i^1].to])
if (Min>edge[i].cap-edge[i].flow)
Min=edge[i].cap-edge[i].flow;
for (int i=pre[u];i!=-1;i=pre[edge[i^1].to])
{
edge[i].flow+=Min;
edge[i^1].flow-=Min;
}
u=start;
ans+=Min;
continue;
}
bool flag=false;
int v;
for (int i=cur[u];i!=-1;i=edge[i].next)
{
v=edge[i].to;
if (edge[i].cap-edge[i].flow && dep[v]+1==dep[u])
{
flag=true;
cur[u]=pre[v]=i;
break;
}
}
if (flag)
{
u=v;
continue;
}
int Min=N;
for (int i=head[u];i!=-1;i=edge[i].next)
if (edge[i].cap-edge[i].flow && dep[edge[i].to]<Min)
{
Min=dep[edge[i].to];
cur[u]=i;
}
gap[dep[u]]--;
if (!gap[dep[u]]) return ans;
dep[u]=Min+1;
gap[dep[u]]++;
if (u!=start) u=edge[pre[u]^1].to;
}
return ans;
}
struct Node
{
int u,v,c,cost;
}node[MAXN];
int n,m,num;
int cost[MAXN];
int main()
{
// freopen("C:/Users/asus1/Desktop/IN.txt","r",stdin);
int i,j,k,u,v,c,co;
while (scanf("%d%d",&n,&m),(n+m))
{
init();
int all=0;
for (i=1;i<=m;i++)
{
cost[i]=0;
scanf("%d",&c);
addedge(0,i,c);
all+=c;
}
scanf("%d",&k);
for (i=1;i<=k;i++)
{
scanf("%d%d%d%d",&node[i].u,&node[i].v,&node[i].c,&node[i].cost);
cost[node[i].c]+=node[i].cost;
}
for (i=1;i<=m;i++)
addedge(i,m+1,cost[i]);
for (i=1;i<=k;i++)
{
for (j=1;j<=k;j++)
{
if (i!=j)
{
if (node[i].c!=node[j].c&&node[i].v==node[j].u)
addedge(node[i].c,node[j].c,INF);
}
}
}
printf("%d\n",all-sap(0,m+1,m+2));
}
return 0;
}
Road constructions (hdu 3917 最大权闭合图)
原文：http://blog.csdn.net/u014422052/article/details/45442607