首页 > > 程序设计 > C/C++ >

bzoj1497 [ NOI2006 ] --最大权闭合子图

2018-06-17 23:18:54来源：未知阅读 ()

建模：

将用户群和中转站看成点。对于用户群i，将其向a[i]，b[i]连一条边，将c[i]作为它的权值。对于中转站i，将-p[i]作为它的权值。

然后问题就转化为求图的最大权闭合子图。

图的闭合子图是指一个点集V，满足对于任意i∈V，i的所有出边指向的点∈V。

根据定义可以知道，图的闭合子图是允许超过一个联通块的。

图的最大权闭合子图是一个图中权值和最大的闭合子图。

怎么求一个图的最大权闭合子图呢？

我们可以用最小割模型解决。

对于一个图G，通过下列操作将其转化为网络N=(V_N,E_N)

1、对于图中的每条有向边(u,v)，连一条容量为无穷大的边(u,v)

2、对于图中的点v(w_v>0)，连一条容量为w_v的边(s,v)

3、对于图中的点v(w_v<0)，连一条容量为-w_v的边(v,t)

那么图的最大权闭合子图就是Σw_v(w_v>0)-maxflow(N)

证明就不说了(因为我不会)

代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 #define N 5010
 6 #define M 50010
 7 #define INF 2147483647
 8 struct Edge{
 9   int t,c,f,nx;
10 }e[N+(M<<1)<<2];
11 int i,j,k,n,m,s,t,h[N+M],Num=1,x,y,Sum,Cur[N+M],q[N+M],l,r,d[N+M];
12 bool b[N+M];
13 inline int _Min(int x,int y){return x<y?x:y;}
14 inline void Add(int x,int y,int c){
15   e[++Num].t=y;e[Num].c=c;e[Num].nx=h[x];h[x]=Num;
16   e[++Num].t=x;e[Num].nx=h[y];h[y]=Num;
17 }
18 inline bool Bfs(){
19   l=0;r=1;memset(b,0,sizeof(b));
20   q[1]=s;b[0]=d[0]=1;
21   while(++l<=r){
22     for(int i=h[q[l]];i;i=e[i].nx)
23       if(e[i].c>e[i].f&&!b[e[i].t]){
24     b[e[i].t]=1;d[e[i].t]=d[q[l]]+1;q[++r]=e[i].t;
25       }
26   }
27   return b[t];
28 }
29 inline int Dfs(int x,int a){
30   if(a==0||x==t)return a;
31   int f,F=0;
32   for(int& i=Cur[x];i;i=e[i].nx)
33     if(d[x]+1==d[e[i].t]&&(f=Dfs(e[i].t,_Min(a,e[i].c-e[i].f)))){
34       F+=f;a-=f;e[i].f+=f;e[i^1].f-=f;
35       if(a==0)break;
36     }
37   if(F==0)d[x]=-1;
38   return F;
39 }
40 inline int Dinic(){
41   int f=0;
42   while(Bfs()){
43     for(int i=s;i<=t;i++)Cur[i]=h[i];
44     f+=Dfs(s,INF);
45   }
46   return f;
47 }
48 int main()
49 {
50   scanf("%d%d",&n,&m);
51   s=0;t=n+m+1;
52   for(i=1;i<=n;i++)scanf("%d",&x),Add(i,t,x);
53   for(i=1;i<=m;i++){
54     scanf("%d%d%d",&x,&y,&k);
55     Sum+=k;
56     Add(i+n,x,INF);
57     Add(i+n,y,INF);
58     Add(s,i+n,k);
59   }
60   printf("%d",Sum-Dinic());
61   return 0;
62 }