目录
显示
题目链接
https://www.luogu.org/problem/P1345
题解
可以看出,本题是让我们求图中的最小割点。
我们可以将每个点拆成两个点,一个点与该点的所有入边相连,一个点连接该点的所有出边,然后在入点和出点之间连一条容量为 \(1\) 的边。
而对于图中的其他边,它们的容量都可以设为正无穷。
于是,我们就把最小割点转化成了我们所熟悉的最小割问题。
跑一遍最大流即可。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define INF 0x3f3f3f3f
using namespace std;
struct edge
{
int v,w,next;
}e[5005];
struct pre
{
int v,e;
}p[5005];
int head[205],vis[205];
int n,m,c1,c2,cnt=1;
void addedge(int u,int v,int w)
{
e[++cnt].v=v;
e[cnt].w=w;
e[cnt].next=head[u];
head[u]=cnt;
}
bool bfs()
{
queue<int> q;
memset(p,0,sizeof(p));
memset(vis,0,sizeof(vis));
vis[c1+n]=1;
q.push(c1+n);
while(!q.empty())
{
int cur=q.front();
q.pop();
for(int i=head[cur];i;i=e[i].next)
if((!vis[e[i].v])&&e[i].w)
{
p[e[i].v].v=cur;
p[e[i].v].e=i;
if(e[i].v==c2)return 1;
vis[e[i].v]=1;
q.push(e[i].v);
}
}
return 0;
}
int main()
{
scanf("%d%d%d%d",&n,&m,&c1,&c2);
for(int i=1;i<=n;i++)
addedge(i,i+n,1),addedge(i+n,i,0);
for(int i=1;i<=m;i++)
{
int u,v;
scanf("%d%d",&u,&v);
addedge(u+n,v,INF);
addedge(v,u+n,0);
addedge(v+n,u,INF);
addedge(u,v+n,0);
}
int ans=0;
while(bfs())
{
int minw=INF;
for(int i=c2;i!=c1+n;i=p[i].v)
minw=min(minw,e[p[i].e].w);
for(int i=c2;i!=c1+n;i=p[i].v)
{
e[p[i].e].w-=minw;
e[p[i].e^1].w+=minw;
}
ans+=minw;
}
printf("%d\n",ans);
return 0;
}
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define INF 0x3f3f3f3f
using namespace std;
struct edge
{
int v,w,next;
}e[5005];
struct pre
{
int v,e;
}p[5005];
int head[205],vis[205];
int n,m,c1,c2,cnt=1;
void addedge(int u,int v,int w)
{
e[++cnt].v=v;
e[cnt].w=w;
e[cnt].next=head[u];
head[u]=cnt;
}
bool bfs()
{
queue<int> q;
memset(p,0,sizeof(p));
memset(vis,0,sizeof(vis));
vis[c1+n]=1;
q.push(c1+n);
while(!q.empty())
{
int cur=q.front();
q.pop();
for(int i=head[cur];i;i=e[i].next)
if((!vis[e[i].v])&&e[i].w)
{
p[e[i].v].v=cur;
p[e[i].v].e=i;
if(e[i].v==c2)return 1;
vis[e[i].v]=1;
q.push(e[i].v);
}
}
return 0;
}
int main()
{
scanf("%d%d%d%d",&n,&m,&c1,&c2);
for(int i=1;i<=n;i++)
addedge(i,i+n,1),addedge(i+n,i,0);
for(int i=1;i<=m;i++)
{
int u,v;
scanf("%d%d",&u,&v);
addedge(u+n,v,INF);
addedge(v,u+n,0);
addedge(v+n,u,INF);
addedge(u,v+n,0);
}
int ans=0;
while(bfs())
{
int minw=INF;
for(int i=c2;i!=c1+n;i=p[i].v)
minw=min(minw,e[p[i].e].w);
for(int i=c2;i!=c1+n;i=p[i].v)
{
e[p[i].e].w-=minw;
e[p[i].e^1].w+=minw;
}
ans+=minw;
}
printf("%d\n",ans);
return 0;
}
#include <cstdio> #include <cstring> #include <algorithm> #include <queue> #define INF 0x3f3f3f3f using namespace std; struct edge { int v,w,next; }e[5005]; struct pre { int v,e; }p[5005]; int head[205],vis[205]; int n,m,c1,c2,cnt=1; void addedge(int u,int v,int w) { e[++cnt].v=v; e[cnt].w=w; e[cnt].next=head[u]; head[u]=cnt; } bool bfs() { queue<int> q; memset(p,0,sizeof(p)); memset(vis,0,sizeof(vis)); vis[c1+n]=1; q.push(c1+n); while(!q.empty()) { int cur=q.front(); q.pop(); for(int i=head[cur];i;i=e[i].next) if((!vis[e[i].v])&&e[i].w) { p[e[i].v].v=cur; p[e[i].v].e=i; if(e[i].v==c2)return 1; vis[e[i].v]=1; q.push(e[i].v); } } return 0; } int main() { scanf("%d%d%d%d",&n,&m,&c1,&c2); for(int i=1;i<=n;i++) addedge(i,i+n,1),addedge(i+n,i,0); for(int i=1;i<=m;i++) { int u,v; scanf("%d%d",&u,&v); addedge(u+n,v,INF); addedge(v,u+n,0); addedge(v+n,u,INF); addedge(u,v+n,0); } int ans=0; while(bfs()) { int minw=INF; for(int i=c2;i!=c1+n;i=p[i].v) minw=min(minw,e[p[i].e].w); for(int i=c2;i!=c1+n;i=p[i].v) { e[p[i].e].w-=minw; e[p[i].e^1].w+=minw; } ans+=minw; } printf("%d\n",ans); return 0; }