《进阶指南》0x60 图论

0x6A 网络流初步

图论的第十部分,网络流初步。

舞动的夜晚

题目描述

L 公司和 H 公司举办了一次联谊晚会。

晚会上,L 公司的 \(N\) 位员工和 H 公司的 \(M\) 位员工打算进行一场交际舞。

在这些领导中,一些 L 公司的员工和 H 公司的员工之间是互相认识的,这样的认识关系一共有 \(T\) 对。

舞会上,每位员工会尝试选择一名 Ta 认识的对方公司的员工作为舞伴,并且每位员工至多跳一支舞。

完成的交际舞的数量越多,晚会的气氛就越热烈。

顾及到晚会的气氛,员工们希望知道,哪些员工之间如果进行了交际舞,就会使整场晚会能够完成的交际舞的最大数量减小。

数据范围

\(1\leq N,M\leq 10^4\),\(1\leq T\leq 10^5\),\(1\leq x\leq N\),\(1\leq y\leq M\)。

题解

求二分图的不可行边,板子题。用 \(\texttt{dinic}\) 算法求解最大流后在残余网络上跑 \(\texttt{tarjan}\) 算法即可。

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
	reg char ch=getchar();
	reg int res=0;
	while(ch<'0'||'9'<ch)ch=getchar();
	while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
	return res;
}

inline void cMin(reg int &a,reg int b){
	if(a>b)
		a=b;
	return;
}

const int MAXN=1e4+5;
const int MAXM=1e4+5;
const int MAXT=1e5+5;
const int MAXV=2*MAXN;
const int MAXE=(MAXN*2+MAXT)*2;
const int inf=0x3f3f3f3f;

int n,m,T;
int cnt=1,head[MAXV],to[MAXE],w[MAXE],Next[MAXE];
int id[MAXE];
vector<int> G[MAXV];

inline void Add_Edge(reg int u,reg int v,reg int len){
	Next[++cnt]=head[u];
	to[cnt]=v;
	w[cnt]=len;
	head[u]=cnt;
	return;
}

inline void Add_Tube(reg int u,reg int v,reg int len){
	Add_Edge(u,v,len);
	Add_Edge(v,u,0);
	return;
}

int dep[MAXV];
queue<int> Q;

inline bool bfs(int s,reg int t){
	memset(dep,-1,sizeof(dep));
	dep[s]=1,Q.push(s);
	while(!Q.empty()){
		reg int u=Q.front();
		Q.pop();
		for(reg int i=head[u];i;i=Next[i]){
			int v=to[i];
			if(dep[v]==-1&&w[i]){
				dep[v]=dep[u]+1;
				Q.push(v);
			}
		}
	}
	return dep[t]!=-1;
}

int cur[MAXV];

inline int dfs(reg int u,reg int t,reg int lim){
	if(u==t)
		return lim;
	reg int flow=0;
	for(reg int &i=cur[u];i;i=Next[i]){
		reg int v=to[i];
		if(dep[v]==dep[u]+1&&w[i]){
			reg int f=dfs(v,t,min(lim-flow,w[i]));
			if(f){
				flow+=f;
				w[i]-=f;
				w[i^1]+=f;
				if(flow==lim)
					break;
			}
		}
	}
	return flow;
}

inline int dinic(reg int s,reg int t){
	reg int res=0;
	while(bfs(s,t)){
		memcpy(cur,head,sizeof(head));
		res+=dfs(s,t,inf);
	}
	return res;
}

bool vis[MAXV];
int tim,dfn[MAXV],low[MAXV];
int top,S[MAXV];
int scc_cnt,col[MAXV];

inline void tarjan(reg int u){
	vis[u]=true;
	dfn[u]=low[u]=++tim;
	S[++top]=u;
	for(reg int i=0,siz=G[u].size();i<siz;++i){
		reg int v=G[u][i];
		if(!dfn[v]){
			tarjan(v);
			cMin(low[u],low[v]);
		}
		else if(vis[v])
			cMin(low[u],dfn[v]);
	}
	if(dfn[u]==low[u]){
		reg int v;
		++scc_cnt;
		do{
			v=S[top--];
			vis[v]=false;
			col[v]=scc_cnt;
		}while(u!=v);
	}
	return;
}

int main(void){
	n=read(),m=read(),T=read();
	int s=0,t=n+m+1;
	for(reg int i=1;i<=n;++i)
		Add_Tube(s,i,1);
	for(reg int i=1;i<=m;++i)
		Add_Tube(i+n,t,1);
	for(reg int i=1;i<=T;++i){
		static int x,y;
		x=read(),y=read();
		Add_Tube(x,n+y,1);
		id[i]=cnt;
	}
	dinic(s,t);
	for(reg int i=1;i<=T;++i)
		if(!w[id[i]]){
			int u=to[id[i]],v=to[id[i]^1];
			G[u].push_back(v);
		}
		else{
			int u=to[id[i]^1],v=to[id[i]];
			G[u].push_back(v);
		}
	for(int i=1;i<=n;++i)
		if(!w[2*i])
			G[i].push_back(s);
		else
			G[s].push_back(i);
	for(reg int i=1;i<=m;++i)
		if(!w[2*(n+i)])
			G[t].push_back(n+i);
		else
			G[n+i].push_back(t);
	for(reg int i=s;i<=t;++i)
		if(!dfn[i])
			tarjan(i);
	reg int top=0;
	for(reg int i=1;i<=T;++i)
		if(!w[id[i]]&&col[to[id[i]]]!=col[to[id[i]^1]])
			S[++top]=i;
	printf("%d\n",top);
	if(!top)
		puts("");
	else
		for(reg int i=1;i<=top;++i)
			printf("%d%c",S[i],i==top?'\n':' ');
	return 0;
}

有线电视网络 Cable TV Network

题目

给定一张 \(n\) 个点 \(m\) 条边的无向图,求最少去掉多少个点,可以使图不连通。

如果不管去掉多少个点,都无法使原图不连通,则直接返回 \(n\)。

数据范围

\(0\leq n\leq 50\)。

题解

网络流经典技巧,点 \(\to\) 边,这里边的流量为 \(1\),之后枚举源点和汇点,跑最小割即可。

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;

const int MAXN=50+5;
const int MAXM=MAXN*(MAXN-1)/2;
const int MAXV=2*MAXN;
const int MAXE=1e4+5;
const int inf=0x3f3f3f3f;

int n,m;
int cnt,head[MAXV],to[MAXE],w[MAXE],Next[MAXE];
int W[MAXE];

inline void Add_Edge(reg int u,reg int v,reg int len){
	Next[++cnt]=head[u];
	to[cnt]=v;
	w[cnt]=len;
	head[u]=cnt;
	return;
}

inline void Add_Tube(reg int u,reg int v,reg int len){
	Add_Edge(u,v,len);
	Add_Edge(v,u,0);
	return;
}

int dep[MAXV];
queue<int> Q;

inline bool bfs(int s,reg int t){
	memset(dep,-1,sizeof(dep));
	dep[s]=1,Q.push(s);
	while(!Q.empty()){
		reg int u=Q.front();
		Q.pop();
		for(reg int i=head[u];i;i=Next[i]){
			int v=to[i];
			if(dep[v]==-1&&w[i]){
				dep[v]=dep[u]+1;
				Q.push(v);
			}
		}
	}
	return dep[t]!=-1;
}

int cur[MAXV];

inline int dfs(reg int u,reg int t,reg int lim){
	if(u==t)
		return lim;
	reg int flow=0;
	for(reg int &i=cur[u];i;i=Next[i]){
		reg int v=to[i];
		if(dep[v]==dep[u]+1&&w[i]){
			reg int f=dfs(v,t,min(lim-flow,w[i]));
			if(f){
				flow+=f;
				w[i]-=f;
				w[i^1]+=f;
				if(flow==lim)
					break;
			}
		}
	}
	return flow;
}

inline int dinic(reg int s,reg int t){
	reg int res=0;
	while(bfs(s,t)){
		memcpy(cur,head,sizeof(head));
		res+=dfs(s,t,inf);
	}
	return res;
}

int main(void){
	while(scanf("%d%d",&n,&m)==2){
		cnt=1,memset(head,0,sizeof(head));
		for(reg int i=1;i<=n;++i)
			Add_Tube(i,i+n,1);
		for(reg int i=1;i<=m;++i){
			static char ch;
			static int x,y;
			cin>>ch,scanf("%d,%d",&x,&y),cin>>ch;
			++x,++y;
			Add_Tube(x+n,y,inf);
			Add_Tube(y+n,x,inf);
		}
		memcpy(W,w,sizeof(w));
		int ans=n;
		for(reg int s=n+1;s<=2*n;++s)
			for(reg int t=s-n+1;t<=n;++t){
				memcpy(w,W,sizeof(W));
				ans=min(ans,dinic(s,t));
			}
		printf("%d\n",ans);
	}
	return 0;
}

K 方格取数

题目描述

在一个 \(N\times N\) 的矩形网格中,每个格子里都写着一个非负整数。

可以从左上角到右下角安排 \(K\) 条路线,每一步只能往下或往右,沿途经过的格子中的整数会被取走。

若多条路线重复经过一个格子,只取一次。

求能取得的整数的和最大是多少。

数据范围

\(1\leq N\leq 50\),\(0\leq K\leq 10\)。

题解

每个点拆成两条边,\(\left<u,u+n^2,1\right>\),权值为格子内的数,\(\left<u,u+n^2,K-1\right>\) 权值为 \(0\),跑费用流即可。

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
	reg char ch=getchar();
	reg int res=0;
	while(ch<'0'||'9'<ch)ch=getchar();
	while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
	return res;
}

const int MAXN=50+5;
const int MAXV=2*MAXN*MAXN;
const int MAXE=(MAXN*MAXN*4)*2;
const int inf=0x3f3f3f3f;

int n,k;
int cnt=1,head[MAXV],to[MAXE],w[MAXE],p[MAXE],Next[MAXE];

inline void Add_Edge(reg int u,reg int v,reg int len,reg int val){
	Next[++cnt]=head[u];
	to[cnt]=v;
	w[cnt]=len;
	p[cnt]=val;
	head[u]=cnt;
	return;
}

inline void Add_Tube(reg int u,reg int v,reg int len,reg int val){
	Add_Edge(u,v,len,val);
	Add_Edge(v,u,0,-val);
	return;
}

bool inque[MAXV];
int dis[MAXV];
queue<int> Q;

inline bool spfa(int s,reg int t){
	memset(dis,0x3f,sizeof(dis));
	inque[s]=true,dis[s]=0,Q.push(s);
	while(!Q.empty()){
		reg int u=Q.front();
		Q.pop();
		inque[u]=false;
		for(reg int i=head[u];i;i=Next[i]){
			int v=to[i];
			if(dis[v]>dis[u]+p[i]&&w[i]){
				dis[v]=dis[u]+p[i];
				if(!inque[v]){
					inque[v]=true;
					Q.push(v);
				}
			}
		}
	}
	return dis[t]!=inf;
}

int Cost;
bool vis[MAXV];
int cur[MAXV];

inline int dfs(reg int u,reg int t,reg int lim){
	if(u==t){
		Cost+=lim*dis[u];
		return lim;
	}
	vis[u]=true;
	reg int flow=0;
	for(reg int &i=cur[u];i;i=Next[i]){
		reg int v=to[i];
		if(dis[v]==dis[u]+p[i]&&w[i]&&!vis[v]){
			reg int f=dfs(v,t,min(lim-flow,w[i]));
			if(f){
				flow+=f;
				w[i]-=f;
				w[i^1]+=f;
				if(flow==lim)
					break;
			}
		}
	}
	vis[u]=false;
	return flow;
}

inline int dinic(reg int s,reg int t){
	reg int res=0;
	while(spfa(s,t)){
		memcpy(cur,head,sizeof(head));
		res+=dfs(s,t,inf);
	}
	return res;
}

int main(void){
	n=read(),k=read();
	reg int n2=n*n,id=0;
	for(reg int i=1;i<=n;++i)
		for(reg int j=1;j<=n;++j){
			static int a;
			a=read();
			++id;
			Add_Tube(id,id+n2,1,-a);
			Add_Tube(id,id+n2,k-1,0);
			if(i<n)
				Add_Tube(id+n2,id+n,k,0);
			if(j<n)
				Add_Tube(id+n2,id+1,k,0);
		}
	dinic(1,n2+n2);
	printf("%d\n",-Cost);
	return 0;
}
Pages: 1 2 3 4 5 6 7 8 9 10 11 12