Loading [MathJax]/extensions/tex2jax.js

[洛谷 1345]Telecowmunication

题目链接

https://www.luogu.org/problem/P1345

题解

可以看出,本题是让我们求图中的最小割点。

我们可以将每个点拆成两个点,一个点与该点的所有入边相连,一个点连接该点的所有出边,然后在入点和出点之间连一条容量为 \(1\) 的边。

而对于图中的其他边,它们的容量都可以设为正无穷。

于是,我们就把最小割点转化成了我们所熟悉的最小割问题。

跑一遍最大流即可。

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#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;
}

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

这个站点使用 Akismet 来减少垃圾评论。了解你的评论数据如何被处理