最大权闭合图

poj2987 Firing http://poj.org/problem?id=2987

最大权闭合图模板题。闭合图就是，对于一个点集V，如果他们的所有的边所指向的点都在点集V中，则这个点集加上他们的边是闭合图。

这种题就是每个点有权值正负零都有可能，选某个点u，如果必须选v，则我们设u，v有一条有向边。最后要我们有一种选取方案使得所选的点权值和最大。这就是最大权闭合图。

解法用的是最大流来解。

最大流==最小割

最小割=减掉流量总和最少的一些边使得源点s和汇点t不连通。

建图方法是：s源点到所有正权点连流量为那个点权值的边，所有负权点到汇点t连流量为负权绝对值的边。原来图中的依赖关系正常建边，流量定为inf。

跑出来的最大流就是最小割。用所有正权的和减去最小割就是可获得的最大权。

证明，因为中间的都是inf，所以最小割肯定是割到与s连的或者与t连的边。那么就是我们选择一些正权或者负权，并且我们都是选小的。也就是说对于正权到s这里，如果正权很小，并且选他就必须选一些负权很大的边，那么我们在最小割中也会选这个正权小的，使得st不连通。反之，如果负权那里小，我们就会选择割负权。最后正权的总和减去最小割。

接下来就是算最小割时候的最少点，即第一问。第一问问的是最少解雇几个人，解雇是挣钱的，也就是最小割不会割到的，也就是边上还有流量的，所以dfs判断是看边流量是否为零，如果不为零说明没被最小割割到，说明解雇这个人是挣钱的，ans++。

从源点dfs去搜索残留网络，因为和源点连接的点都是权值为正的，是我们要解雇的人的集合，如果残留网络的边还为正，则这时候则表示fire这个点可以有收益。

dinic

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<queue>
  4 #define mt(a,b) memset(a,b,sizeof(a))
  5 using namespace std;
  6 typedef __int64 LL;
  7 const LL inf=0x3f3f3f3f3f3f3f3fLL;
  8 class Dinic { ///最大流(MV^2*ME)
  9     typedef LL typef;///流量的类型
 10     static const int ME=1000000;///边的个数
 11     static const int MV=5010;///点的个数
 12     int temp[MV],cur[MV],level[MV],path[MV];
 13     bool used[MV];
 14     queue<int> q;
 15     typef flow;
 16     bool bfs(int s,int t) {
 17         mt(level,-1);
 18         while(!q.empty()) q.pop();
 19         q.push(s);
 20         level[s]=1;
 21         while(!q.empty()) {
 22             int u=q.front();
 23             q.pop();
 24             for(int i=g.head[u]; ~i; i=g.e[i].next) {
 25                 int v=g.e[i].v;
 26                 if(level[v]==-1&&g.e[i].flow) {
 27                     level[v]=level[u]+1;
 28                     q.push(v);
 29                     if(v==t) return true;
 30                 }
 31             }
 32         }
 33         return false;
 34     }
 35 public:
 36     struct G {
 37         struct E {
 38             int u,v,next;
 39             typef flow;
 40         } e[ME];
 41         int le,head[MV];
 42         void init() {
 43             le=0;
 44             mt(head,-1);
 45         }
 46         void add(int u,int v,typef flow) {
 47             e[le].u=u;
 48             e[le].v=v;
 49             e[le].flow=flow;
 50             e[le].next=head[u];
 51             head[u]=le++;
 52         }
 53     } g;
 54 public:
 55     typef getflow() {
 56         return flow;
 57     }
 58     void init() {
 59         g.init();
 60     }
 61     void add(int u,int v,typef flow) {
 62         g.add(u,v,flow);
 63         g.add(v,u,0);
 64     }
 65     void solve(int s,int t) {
 66         int p,tempp;
 67         typef now;
 68         bool flag;
 69         flow=0;
 70         while(bfs(s,t)) {
 71             for(int i=0; i<MV; i++) {
 72                 temp[i]=g.head[i];
 73                 used[i]=true;
 74             }
 75             p=1;
 76             path[p]=s;
 77             while(p) {
 78                 int u=path[p];
 79                 if(u==t) {
 80                     now=inf;
 81                     for(int i=1; i<p; i++) {
 82                         now=min(now,g.e[cur[path[i]]].flow);
 83                     }
 84                     flow+=now;
 85                     for(int i=1; i<p; i++) {
 86                         int j=cur[path[i]];
 87                         g.e[j].flow-=now;
 88                         g.e[j^1].flow+=now;
 89                         if(!g.e[j].flow) tempp=i;
 90                     }
 91                     p=tempp;
 92                 } else {
 93                     flag=false;
 94                     for(int i=temp[u]; ~i; i=g.e[i].next) {
 95                         int v=g.e[i].v;
 96                         if(used[v]&&g.e[i].flow&&level[u]+1==level[v]) {
 97                             cur[u]=i;
 98                             temp[u]=g.e[i].next;
 99                             flag=true;
100                             path[++p]=v;
101                             break;
102                         }
103                     }
104                     if(flag) continue;
105                     p--;
106                     used[u]=false;
107                 }
108             }
109         }
110     }
111 } dinic;
112 bool vis[5010];
113 void dfs(int u,int t) {
114     if(u==t) return ;
115     vis[u]=true;
116     for(int i=dinic.g.head[u]; ~i; i=dinic.g.e[i].next) {
117         int v=dinic.g.e[i].v;
118         if(dinic.g.e[i].flow&&!vis[v]) {
119             dfs(v,t);
120         }
121     }
122 }
123 int main() {
124     int n,m;
125     while(~scanf("%d%d",&n,&m)) {
126         dinic.init();
127         LL sum=0;
128         int s=0,t=n+1;
129         for(int i=1,val; i<=n; i++) {
130             scanf("%d",&val);
131             if(val>0) {
132                 sum+=val;
133                 dinic.add(s,i,val);
134             } else {
135                 dinic.add(i,t,-val);
136             }
137         }
138         while(m--) {
139             int u,v;
140             scanf("%d%d",&u,&v);
141             dinic.add(u,v,inf);
142         }
143         dinic.solve(s,t);
144         mt(vis,0);
145         dfs(s,t);
146         int ans=0;
147         for(int i=1; i<=n; i++) {
148             if(vis[i]) ans++;
149         }
150         printf("%d %I64d
",ans,sum-dinic.getflow());
151     }
152     return 0;
153 }

View Code

sap

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<queue>
  4 #define mt(a,b) memset(a,b,sizeof(a))
  5 using namespace std;
  6 typedef __int64 LL;
  7 const LL inf=0x3f3f3f3f3f3f3f3fLL;
  8 class Sap { ///最大流 O(MV*ME^2)
  9     typedef LL typef;///流量的类型
 10     static const int ME=1000000;///边的个数
 11     static const int MV=5010;///点的个数
 12     int n,dep[MV],gap[MV],cur[MV],S[MV],top,i,inser;
 13     typef flow;
 14     queue<int> q;
 15     void bfs(int s,int t) {
 16         mt(dep,-1);
 17         mt(gap,0);
 18         while(!q.empty()) q.pop();
 19         gap[0]=1;
 20         dep[t]=0;
 21         q.push(t);
 22         while(!q.empty()) {
 23             int u=q.front();
 24             q.pop();
 25             for(int i=g.head[u]; ~i; i=g.e[i].next) {
 26                 int v=g.e[i].v;
 27                 if(dep[v]!=-1) continue;
 28                 q.push(v);
 29                 dep[v]=dep[u]+1;
 30                 ++gap[dep[v]];
 31             }
 32         }
 33     }
 34 public:
 35     struct G {
 36         struct E {
 37             int u,v,next;
 38             typef flow;
 39         } e[ME];
 40         int le,head[MV];
 41         void init() {
 42             le=0;
 43             mt(head,-1);
 44         }
 45         void add(int u,int v,typef flow) {
 46             e[le].u=u;
 47             e[le].v=v;
 48             e[le].flow=flow;
 49             e[le].next=head[u];
 50             head[u]=le++;
 51         }
 52     } g;
 53 public:
 54     void init(int tn) {///传入点的个数
 55         n=tn;
 56         g.init();
 57     }
 58     void add(int u,int v,typef flow) {
 59         g.add(u,v,flow);
 60         g.add(v,u,0);
 61     }
 62     typef solve(int s,int t) {
 63         bfs(s,t);
 64         flow=top=0;
 65         for(i=0;i<=n;i++) cur[i]=g.head[i];
 66         int u=s;
 67         while(dep[s]<n) {
 68             if(u==t) {
 69                 int temp=inf;
 70                 for(i=0; i<top; i++)
 71                     if(temp>g.e[S[i]].flow) {
 72                         temp=g.e[S[i]].flow;
 73                         inser=i;
 74                     }
 75                 for(i=0; i<top; i++) {
 76                     g.e[S[i]].flow-=temp;
 77                     g.e[S[i]^1].flow+=temp;
 78                 }
 79                 flow+=temp;
 80                 top=inser;
 81                 u=g.e[S[top]].u;
 82             }
 83             if(u!=t&&!gap[dep[u]-1]) break;
 84             for(i=cur[u]; ~i; i=g.e[i].next)
 85                 if(g.e[i].flow&&dep[u]==dep[g.e[i].v]+1)
 86                     break;
 87             if(~i) {
 88                 cur[u]=i;
 89                 S[top++]=i;
 90                 u=g.e[i].v;
 91             } else {
 92                 int sma=n;
 93                 for(i=g.head[u]; ~i; i=g.e[i].next) {
 94                     if(!g.e[i].flow) continue;
 95                     int v=g.e[i].v;
 96                     if(sma>dep[v]) {
 97                         sma=dep[v];
 98                         cur[u]=i;
 99                     }
100                 }
101                 --gap[dep[u]];
102                 dep[u]=sma+1;
103                 ++gap[dep[u]];
104                 if(u!=s) u=g.e[S[--top]].u;
105             }
106         }
107         return flow;
108     }
109 }sap;
110 
111 bool vis[5010];
112 void dfs(int u,int t) {
113     if(u==t) return ;
114     vis[u]=true;
115     for(int i=sap.g.head[u]; ~i; i=sap.g.e[i].next) {
116         int v=sap.g.e[i].v;
117         if(sap.g.e[i].flow&&!vis[v]) {
118             dfs(v,t);
119         }
120     }
121 }
122 int main() {
123     int n,m;
124     while(~scanf("%d%d",&n,&m)) {
125         sap.init(n+2);
126         LL sum=0;
127         int s=0,t=n+1;
128         for(int i=1,val; i<=n; i++) {
129             scanf("%d",&val);
130             if(val>0) {
131                 sum+=val;
132                 sap.add(s,i,val);
133             } else {
134                 sap.add(i,t,-val);
135             }
136         }
137         while(m--) {
138             int u,v;
139             scanf("%d%d",&u,&v);
140             sap.add(u,v,inf);
141         }
142         LL flow=sap.solve(s,t);
143         mt(vis,0);
144         dfs(s,t);
145         int ans=0;
146         for(int i=1; i<=n; i++) {
147             if(vis[i]) ans++;
148         }
149         printf("%d %I64d
",ans,sum-flow);
150     }
151     return 0;
152 }

View Code

end