「网络流 24 题」太空飞行计划

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 
  4 int m,n,tot=-1,h[10005],ans=0,bianhao[505][505],co[505],sum=0;
  5 bool wll[10005];
  6 struct node{
  7     int from,next,to,rest;
  8     int last;
  9 }e[100005];
 10 
 11 void add(int x,int y,int z){
 12     tot++;
 13     e[tot].next=h[x];
 14     h[x]=tot;
 15     e[tot].from=x;
 16     e[tot].to=y;
 17     e[tot].rest=z;
 18 }
 19 
 20 int dis[10005],g[10005],flow[10005];
 21 bool vis[10005];
 22 
 23 int bfs(int s,int t){
 24     queue<int>q;
 25     dis[s]=0;
 26     q.push(s);vis[s]=true;
 27     while(!q.empty()){
 28         int u=q.front();vis[u]=false;q.pop();
 29         for(int i=h[u];i!=(-1);i=e[i].next){
 30             if(dis[e[i].to]>dis[u]+1&&g[e[i].to]==(-1)&&e[i].rest>0){
 31                 g[e[i].to]=i;
 32                 flow[e[i].to]=min(flow[u],e[i].rest);
 33                 dis[e[i].to]=dis[u]+1;
 34                 if(vis[e[i].to]==false){
 35                     vis[e[i].to]=true;
 36                     q.push(e[i].to);
 37                 }
 38             }
 39         }
 40     }
 41 }
 42 
 43 int EK(int s,int t){
 44     while(1){
 45         bfs(s,t);
 46         if(g[t]==(-1))return 0;
 47         ans+=flow[t];
 48         for(int p=t;p!=(s);p=e[g[p]].from){
 49             e[g[p]].rest-=flow[t];
 50             e[g[p]^1].rest+=flow[t];
 51         }    
 52         memset(dis,0x7f,sizeof(dis));
 53         memset(vis,false,sizeof(vis));
 54         memset(flow,0x7f,sizeof(flow));
 55         memset(g,-1,sizeof(g));
 56     }
 57 }
 58 
 59 int main(){
 60     //freopen("shut1.in","r",stdin);
 61     memset(dis,0x7f,sizeof(dis));
 62     memset(vis,false,sizeof(vis));
 63     memset(flow,0x7f,sizeof(flow));
 64     memset(g,-1,sizeof(g)); 
 65     memset(h,(-1),sizeof(h));
 66     memset(bianhao,0,sizeof(bianhao));
 67     cin>>m>>n;
 68     for(int i=1;i<=m;i++){
 69         int mo,k;cin>>mo;sum+=mo;
 70         add(0,i,mo);
 71         add(i,0,0);
 72         char a;
 73         while(1){
 74             a=getchar();if(a=='
'||a=='
'||a==EOF)break;
 75             bianhao[i][0]++;
 76             cin>>bianhao[i][bianhao[i][0]];
 77         }
 78     }
 79     for(int i=1;i<=n;i++){
 80         cin>>co[i];
 81         add(m+i,m+n+1,co[i]);
 82         add(m+n+1,m+i,0);
 83     }
 84     for(int i=1;i<=m;i++){
 85         for(int j=1;j<=bianhao[i][0];j++){
 86             add(i,m+bianhao[i][j],9999999);
 87             add(m+bianhao[i][j],i,0);
 88         }
 89     }
 90     EK(0,m+n+1);
 91     int jk;
 92     for(int i=h[0];i!=(-1);i=e[i].next){
 93         if(dis[e[i].to]<99999){
 94             cout<<e[i].to;
 95             for(int j=1;j<=bianhao[e[i].to][0];j++)wll[bianhao[e[i].to][j]]=true;
 96             jk=e[i].next;
 97             break;
 98         }
 99     }
100     for(int i=jk;i!=(-1);i=e[i].next){
101         if(dis[e[i].to]<99999){
102             for(int j=1;j<=bianhao[e[i].to][0];j++)wll[bianhao[e[i].to][j]]=true;
103             cout<<" "<<e[i].to;
104         }
105     }
106     cout<<endl;
107     for(int i=1;i<=n;i++){
108         if(wll[i]==true){
109             cout<<i;
110             jk=i+1;
111             break;
112         }
113     }
114     for(int i=jk;i<=n;i++){
115         if(wll[i]==true){
116             cout<<" "<<i;
117         }
118     }
119     cout<<endl;
120     cout<<sum-ans<<endl;
121 }

View Code

模型好像叫什么最大独立权....

记不住名字就很烦

定义
有一个有向图，每一个点都有一个权值（可以为正或负或0），选择一个权值和最大的子图，使得每个点的后继都在子图里面，这个子图就叫最大权闭合子图。
如下图：
在这里插入图片描述
考虑网络流,选择一个点,相当于网络流流过去
自然原图可以等价于

看到这个图,先想一下,假设每次我们能选与源点相连的多条边,割掉一条边代表什么??

对于与s链接的边来说,割边相当与不选这个点
对于与t链接的边来说,割边相当于选择这个点,(边权全为正嘛…)
那么我们可以贪心的想一下,我们要原图边权加起来最大,那么是不是要割最小的边

那么我们假设是最小割,那么原图不连通…
不连通意味这什么(s—t不连通),那么就是对于选择的子图,满足选择了选择了的节点的全部后继(应该是吧,应为不存在路啊!!!)
然后就ok了
Q.E.D
那么对于原图直接跑EK或dinic之类的就好了

上面的不是抄袭,是我自己csdn博客的东西