您的位置: 首页  >  IT文章  >  洛谷 P4174 [NOI2006]最大获利 && 洛谷 P2762 太空飞行计划问题 (最大权闭合子图 && 最小割输出任意一组方案)

洛谷 P4174 [NOI2006]最大获利 && 洛谷 P2762 太空飞行计划问题 (最大权闭合子图 && 最小割输出任意一组方案)

分类: IT文章 • 2022-05-11 20:49:06

https://www.luogu.org/problemnew/show/P4174

最大权闭合子图的模板

每个通讯站建一个点，点权为-Pi；每个用户建一个点，点权为Ci，分别向Ai和Bi对应的点连边；然后就可以跑了

方法是：

建新源S和新汇T，从S向所有正权点连边，容量为点权值；从所有负权点向T连边，容量为点权值的相反数；原图中所有边容量设为无穷大

跑S到T最大流

原因：（网上都有，自己研究的也不知道有没有偏差）

找出图的任意一个割，其中：

显然不可能割掉容量为无穷大的边；

割掉一条S到u的边，表示不取点u，同时舍弃u点的价值；

割掉一条v到T的边，表示取点v，同时加上v点的代价；

能保证割完这个割中的边后，S到T不连通，即保证不存在任意路径，从S到u经过一些点到v再到T，即保证不存在一个u点需要被取，但是它能到达的一个节点v没有被取。

因此，一个割对应一种闭合子图方案

同样的，可以证明一种闭合子图方案一定对应这样的一个割。

那么，求出最小割，就求出了最小的"舍弃的价值和"+"加上的代价和"，设其为x，则最大权闭合子图的点权和等于所有正点权和-x，而最小割等于最大流

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<vector>
 5 #include<queue>
 6 using namespace std;
 7 #define fi first
 8 #define se second
 9 #define mp make_pair
10 #define pb push_back
11 typedef long long ll;
12 typedef unsigned long long ull;
13 typedef pair<int,int> pii;
14 namespace F
15 {
16 
17 struct E
18 {
19     int to,nxt,from,cap,flow;
20 }e[400100];
21 int f1[60100],ne=1;
22 int S,T,n;
23 int d[60100];
24 bool bfs()
25 {
26     int k,u;
27     memset(d,0,sizeof(int)*(n+1));
28     queue<int> q;
29     q.push(S);d[S]=1;
30     while(!q.empty())
31     {
32         u=q.front();q.pop();
33         for(k=f1[u];k;k=e[k].nxt)
34             if(!d[e[k].to]&&e[k].cap>e[k].flow)
35             {
36                 d[e[k].to]=d[u]+1;
37                 //if(e[k].to==T)    return 1;
38                 q.push(e[k].to);
39             }
40     }
41     //return 0;
42     return d[T];
43 }
44 int cur[60100];
45 int dfs(int u,int x)
46 {
47     if(u==T||x==0)    return x;
48     int flow=0,f;
49     for(int &k=cur[u];k;k=e[k].nxt)
50         if(e[k].cap>e[k].flow&&d[e[k].to]==d[u]+1)
51         {
52             f=dfs(e[k].to,min(x-flow,e[k].cap-e[k].flow));
53             e[k].flow+=f;e[k^1].flow-=f;flow+=f;
54             if(flow==x)    return flow;
55         }
56     return flow;
57 }
58 int solve()
59 {
60     int flow=0;
61     while(bfs())
62     {
63         memcpy(cur,f1,sizeof(int)*(n+1));
64         flow+=dfs(S,0x3f3f3f3f);
65     }
66     return flow;
67 }
68 void me(int a,int b,int c)
69 {
70     e[++ne].to=b;e[ne].nxt=f1[a];f1[a]=ne;
71     e[ne].from=a;e[ne].cap=c;
72     e[++ne].to=a;e[ne].nxt=f1[b];f1[b]=ne;
73     e[ne].from=b;e[ne].cap=0;
74 }
75 
76 }
77 int n,m;
78 int main()
79 {
80     int i,a,b,c,ss=0,t;
81     scanf("%d%d",&n,&m);F::n=n+m+2;F::S=n+m+1;F::T=n+m+2;
82     for(i=1;i<=n;i++)
83     {
84         scanf("%d",&t);
85         F::me(i,F::T,t);
86         //ss-=t;
87     }
88     for(i=1;i<=m;i++)
89     {
90         scanf("%d%d%d",&a,&b,&c);
91         F::me(F::S,i+n,c);
92         F::me(i+n,a,0x3f3f3f3f);
93         F::me(i+n,b,0x3f3f3f3f);
94         ss+=c;
95     }
96     printf("%d",ss-F::solve());
97     return 0;
98 }
View Code

upd20190307:

貌似cf出了重题，但是要改longlonghttps://codeforces.com/problemset/problem/1082/G

https://www.luogu.org/problemnew/show/P2762

这题也是一样，但是要输出方案

按照上面的方法，只要找出任意一组最小割就容易找到输出方法了

怎么找最小割？只要找出跑出最大流以后，找出残量网络中源点S能到达的点集s1，取t1=所有点的集合-s1，那么割掉原图中所有s1,t1间的边即可

这里面有一个看起来比较靠谱的证明：https://hihocoder.com/problemset/problem/1378

  1 #include<cstdio>
  2 #include<algorithm>
  3 #include<cstring>
  4 #include<vector>
  5 #include<queue>
  6 #include<iostream>
  7 using namespace std;
  8 #define fi first
  9 #define se second
 10 #define mp make_pair
 11 #define pb push_back
 12 typedef long long ll;
 13 typedef unsigned long long ull;
 14 typedef pair<int,int> pii;
 15 namespace F
 16 {
 17 
 18 struct E
 19 {
 20     int to,nxt,from,cap,flow;
 21 }e[400100];
 22 int f1[60100],ne=1;
 23 int S,T,n;
 24 int d[60100];
 25 bool bfs()
 26 {
 27     int k,u;
 28     memset(d,0,sizeof(int)*(n+1));
 29     queue<int> q;
 30     q.push(S);d[S]=1;
 31     while(!q.empty())
 32     {
 33         u=q.front();q.pop();
 34         for(k=f1[u];k;k=e[k].nxt)
 35             if(!d[e[k].to]&&e[k].cap>e[k].flow)
 36             {
 37                 d[e[k].to]=d[u]+1;
 38                 //if(e[k].to==T)    return 1;
 39                 q.push(e[k].to);
 40             }
 41     }
 42     //return 0;
 43     return d[T];
 44 }
 45 int cur[60100];
 46 int dfs(int u,int x)
 47 {
 48     if(u==T||x==0)    return x;
 49     int flow=0,f;
 50     for(int &k=cur[u];k;k=e[k].nxt)
 51         if(e[k].cap>e[k].flow&&d[e[k].to]==d[u]+1)
 52         {
 53             f=dfs(e[k].to,min(x-flow,e[k].cap-e[k].flow));
 54             e[k].flow+=f;e[k^1].flow-=f;flow+=f;
 55             if(flow==x)    return flow;
 56         }
 57     return flow;
 58 }
 59 int solve()
 60 {
 61     int flow=0;
 62     while(bfs())
 63     {
 64         memcpy(cur,f1,sizeof(int)*(n+1));
 65         flow+=dfs(S,0x3f3f3f3f);
 66     }
 67     return flow;
 68 }
 69 void me(int a,int b,int c)
 70 {
 71     e[++ne].to=b;e[ne].nxt=f1[a];f1[a]=ne;
 72     e[ne].from=a;e[ne].cap=c;
 73     e[++ne].to=a;e[ne].nxt=f1[b];f1[b]=ne;
 74     e[ne].from=b;e[ne].cap=0;
 75 }
 76 
 77 
 78 }
 79 
 80 int n,m;
 81 char tools[1001000];
 82 bool ok[60100];
 83 int tt[1001000];
 84 void work()
 85 {
 86     int k,u;
 87     memset(ok,0,sizeof(bool)*(n+1));
 88     queue<int> q;
 89     q.push(F::S);ok[F::S]=1;
 90     using F::f1;using F::e;
 91     while(!q.empty())
 92     {
 93         u=q.front();q.pop();
 94         for(k=f1[u];k;k=e[k].nxt)
 95             if(!ok[e[k].to]&&e[k].cap>e[k].flow)
 96             {
 97                 q.push(e[k].to);
 98                 ok[e[k].to]=1;
 99             }
100     }
101     for(int i=1;i<=F::n;i++)
102         if(ok[i])
103         {
104             for(k=f1[i];k;k=e[k].nxt)
105                 if(k%2==0&&!ok[e[k].to])
106                     tt[++tt[0]]=k;
107         }
108 }
109 bool nok[5010];
110 int main()
111 {
112     int i,a,b,c,ss=0,t;
113     scanf("%d%d",&m,&n);F::n=n+m+2;F::S=n+m+1;F::T=n+m+2;
114     for(i=1;i<=m;i++)
115     {
116         scanf("%d",&t);
117         F::me(F::S,i,t);
118         ss+=t;
119         cin.getline(tools,10000);
120         int ulen=0,tool;
121         while(sscanf(tools+ulen,"%d",&tool)==1)
122         {
123             F::me(i,tool+m,0x3f3f3f3f);
124             if(tool==0)
125                 ulen++;
126             else
127             {
128                 while(tool)
129                 {
130                     tool/=10;
131                     ulen++;
132                 }
133             }
134             ulen++;
135         }
136     }
137     for(i=1;i<=n;i++)
138     {
139         scanf("%d",&t);
140         F::me(i+m,F::T,t);
141     }
142     int an=ss-F::solve();
143     work();
144     for(i=1;i<=tt[0];i++)
145     {
146         using F::e;
147         if(e[tt[i]].from==F::S)
148         {
149             nok[e[tt[i]].to]=1;
150         }
151     }
152     for(i=1;i<=m;i++)
153         if(!nok[i])
154             printf("%d ",i);
155     puts("");
156     for(i=1;i<=tt[0];i++)
157     {
158         using F::e;
159         if(e[tt[i]].to==F::T)
160         {
161             printf("%d ",e[tt[i]].from-m);
162         }
163     }
164     puts("");
165     printf("%d",an);
166     return 0;
167 }
View Code

相关推荐