JZOJ 6683. 【2020.06.04省选模拟】我图呢(graph) 题解
题目大意
给你一个二分图，求最大独立集。
输出方案。
解题思路
我们把权值加上
i
n
f
inf
inf后，就是求二分图最大权独立集，这样就不用考虑点数了。
考虑染色出二分图。然后建图：
s
s
s向二分图左边的部分连一条容量为点权加上
i
n
f
inf
inf的边。
二分图的右边部分向
t
t
t连一条容量为点权加上
i
n
f
inf
inf的边。
然后二分图的边连起来，容量为
I
n
f
Inf
Inf（与
i
n
f
inf
inf不同）。
对于这种二元关系的题目。就是求这个网络的最小割。
但答案是总的权值减去最小割。为什么要用总的权值减去最小割？考虑一条边如果被割了，那么相当于把点移除集合。如果不割，相当于留在
T
T
T中。所以求的答案，
T
T
T的最大点权和，为不割的边的边权和。不割也就是总的权值减去最小割。
寻找答案：
- 本题的算法：考虑从
s
s
s开始搜索，在残量网络上找仍可以流的边，然后找到
S
S
S集合。枚举边集，看一看这条边是否过两个集合。这些边是最小割。可知最小割的边的一端一定连着
s
,
t
s,t
s,t，那么我们只要把另一端标记，另一端即为在最小割中的结点。答案求不在最小割中的点。记录一下就可以了。注意时间复杂度为
O
(
n
2
m
)
O(n^2m)
O(n2m)。
- 一般算法：考虑枚举每条边（容量为
c
c
c），设原来的最小割为
c
u
t
1
cut1
cut1，删除这条边后的为
c
u
t
2
cut2
cut2，如果
c
u
t
1
?
c
u
t
2
=
c
cut1-cut2=c
cut1?cut2=c，那么说明这条边有贡献。那么这条边的某一个端点在最小割中。注意每一次如果满足情况，都要把这条边给删去，并且把原来的最小割更新。注意时间复杂度为
O
(
n
2
m
2
)
O(n^2m^2)
O(n2m2)。
#include<bits/stdc++.h>
#define fo(a,b,c) for (ll a=b;a<=c;a++)
using namespace std;
typedef long long ll;
const ll inf=1e9;
const ll inf2=1e18;
ll n,m,w[305],la[305],la2[305],fr[200000],to[200000],ne[200000],cap[200000],flow[200005],cnt=1,s,t,col[305];
ll g[305][305];
void color(ll x,ll c){
col[x]=c;
fo(i,1,g[x][0]){
ll y=g[x][i];
if (!col[y]){
color(y,3-c);
}
}
}
void add(ll x,ll y,ll c){
++cnt;
fr[cnt]=x;
to[cnt]=y;
cap[cnt]=c;
flow[cnt]=0;
ne[cnt]=la[x];
la[x]=cnt;
}
queue<ll>q,q2;
ll a[305],vis[305];
ll bfs(){
memset(vis,0,sizeof(vis));
vis[s]=1;
memset(a,0,sizeof(a));
q=q2;
q.push(s);
while (!q.empty()){
ll x=q.front();
q.pop();
for (ll i=la[x];i;i=ne[i]){
ll y=to[i];
if (cap[i]>flow[i]&&(!vis[y])){
vis[y]=1;
a[y]=a[x]+1;
q.push(y);
}
}
}
return a[t];
}
ll dfs(ll x,ll nowflow){
if (nowflow==0||x==t) return nowflow;
ll sum=0;
for (ll &i=la2[x];i;i=ne[i]){
ll y=to[i];
if (a[x]+1==a[y]){
int f=dfs(y,min(nowflow,cap[i]-flow[i]));
if (f){
sum+=f;
nowflow-=f;
flow[i]+=f;
flow[i^1]-=f;
if (!nowflow) break;
}
}
}
return sum;
}
ll dinic(ll sum){
ll ans=sum;
while (bfs()){
fo(i,1,t) la2[i]=la[i];
ans-=dfs(s,inf2);
}
return ans;
}
ll ins[305],ch[305];
void find(){
q=q2;
q.push(s);
ins[s]=1;
while (!q.empty()){
int x=q.front();
q.pop();
for (ll i=la[x];i;i=ne[i]){
ll y=to[i];
if (cap[i]>flow[i]&&(!ins[y])){
ins[y]=1;
q.push(y);
}
}
}
}
int main(){
freopen("graph.in","r",stdin);
freopen("graph.out","w",stdout);
ll sum=0;
scanf("%lld%lld",&n,&m);
s=n+1;
t=n+2;
fo(i,1,n)scanf("%lld",&w[i]),w[i]+=inf,sum+=w[i];
fo(i,1,m){
ll x,y;
scanf("%lld%lld",&x,&y);
g[x][++g[x][0]]=y;
g[y][++g[y][0]]=x;
}
fo(i,1,n)if(!col[i])color(i,1);
fo(i,1,n){
if (col[i]==1){
add(s,i,w[i]);
add(i,s,0);
}
if (col[i]==2){
add(i,t,w[i]);
add(t,i,0);
}
}
fo(i,1,n){
if (col[i]==1){
fo(j,1,g[i][0]){
ll k=g[i][j];
add(i,k,inf2);
add(k,i,0);
}
}
}
ll ans=dinic(sum);
find();
fo(i,2,cnt){
if (i&1) continue;
if (ins[fr[i]]!=ins[to[i]]){
if (fr[i]==s||fr[i]==t) ch[to[i]]=1;
if (to[i]==s||to[i]==t) ch[fr[i]]=1;
}
}
ll ans1=0;
fo(i,1,n)ans1+=(ch[i]^1);
printf("%lld %lld\n",ans1,ans%inf);
fo(i,1,n)putchar((ch[i]^1)+'0');
}
|