最大权闭合子图

一、模板题：P4174 [NOI2006]最大获利

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 const int MAX=4e5,INF=0x3f3f3f3f,MAXN=4e5;
  4 struct ppp{
  5     int to,next ,flow;
  6 }edge[MAX<<1];
  7 int n,m,tot,s,t,maxflow;
  8 int head[MAXN],cur[MAXN],dep[MAXN],gap[MAXN];
  9 inline void add(int u,int v ,int w)
 10 {
 11     edge[tot]=(ppp){v,head[u],w};
 12     head[u]=tot;
 13     tot++;
 14 }
 15 void bfs()
 16 {
 17     memset(dep,-1,sizeof(dep));
 18     memset(gap,0,sizeof(gap));
 19     dep[t]=0;
 20     gap[dep[t]]=1;
 21     queue<int>q;
 22     q.push(t);
 23     while(!q.empty())
 24     {
 25         int u=q.front();
 26         q.pop();
 27         for(int i=head[u];i!=-1;i=edge[i].next)
 28         {
 29             int v=edge[i].to;
 30             if(dep[v]!=-1)    continue;
 31             q.push(v);
 32             dep[v]=dep[u]+1;
 33             gap[dep[v]]++;
 34         }
 35     }
 36     return;
 37 }
 38 int dfs(int u,int flow)
 39 {
 40     if(u==t)
 41     {
 42         maxflow+=flow;
 43         return flow;
 44     }
 45     int used =0;
 46     for(int i=cur[u];i!=-1;i=edge[i].next)
 47     {
 48         cur[u]=i;
 49         int v=edge[i].to;
 50         if(edge[i].flow and dep[v]+1==dep[u])
 51         {
 52             int low=dfs(v,min(flow-used,edge[i].flow));
 53             if(low)
 54             {
 55                 edge[i].flow-=low;
 56                 edge[i^1].flow+=low;
 57                 used+=low;
 58             }
 59             if(used==flow)    return flow;
 60         }
 61     }
 62     gap[dep[u]]--;
 63     if(gap[dep[u]]==0)    dep[s]=n+m+3;
 64     dep[u]++;
 65     gap[dep[u]]++;
 66     return used;
 67 }
 68 void isap()
 69 {
 70     bfs();
 71     while(dep[s]<n+m+2)
 72     {
 73         memcpy(cur,head,sizeof(head));
 74         dfs(s,INF);
 75     }
 76 }
 77 int main()
 78 {
 79     scanf("%d%d",&n,&m);//1~m user ;m+1~m+n facility
 80     memset(head,-1,sizeof(head));
 81     s=n+m+2,t=n+m+1;
 82     for(int i=1;i<=n;i++)
 83     {
 84         int k;
 85         scanf("%d",&k);
 86         add(m+i,t,k);
 87         add(t,m+i,0);
 88     }
 89     int ans=0;
 90     for(int i=1;i<=m;i++)
 91     {
 92         int a,b,c;
 93         scanf("%d%d%d",&a,&b,&c);
 94         ans+=c;
 95         a+=m,b+=m;
 96         add(i,a,INF);
 97         add(a,i,0);
 98         add(i,b,INF);
 99         add(b,i,0);
100         add(s,i,c);
101         add(i,s,0);
102     }
103     isap();
104     printf("%d",ans-maxflow);
105     return 0;
106 }

View Code

二、建图方式

　　新建原点s，汇点t，将所有正权点与s连接，容量为权值，正权点与负权点的边，容量为INF，负权点与t连边，边权为其权值的绝对值。

三、证明

　　咕咕咕……