【PowerOJ1738&网络流24题】最小路径覆盖问题 (最大流)
2024-09-05 20:59:10
题意:
思路:
【问题分析】
有向无环图最小路径覆盖,可以转化成二分图最大匹配问题,从而用最大流解决。
【建模方法】
构造二分图,把原图每个顶点i拆分成二分图X,Y集合中的两个顶点Xi和Yi。对于原图中存在的每条边(i,j),在二分图中连接边(Xi,Yj)。然后把二分图最大匹配模型转化为网络流模型,求网络最大流。
最小路径覆盖的条数,就是原图顶点数,减去二分图最大匹配数。沿着匹配边查找,就是一个路径上的点,输出所有路径即可。
【建模分析】
对于一个路径覆盖,有如下性质:
1、每个顶点属于且只属于一个路径。
2、路径上除终点外,从每个顶点出发只有一条边指向路径上的另一顶点。
所以我们可以把每个顶点理解成两个顶点,一个是出发,一个是目标,建立二分图模型。该二分图的任何一个匹配方案,都对应了一个路径覆盖方案。如果匹配数为0,那么显然路径数=顶点数。每增加一
条匹配边,那么路径覆盖数就减少一个,所以路径数=顶点数 - 匹配数。要想使路径数最少,则应最大化匹配数,所以要求二分图的最大匹配。
注意,此建模方法求最小路径覆盖仅适用于有向无环图,如果有环或是无向图,那么有可能求出的一些环覆盖,而不是路径覆盖。
DAG的最小路径覆盖=点数-二分图最大匹配
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int> PII;
typedef pair<ll,ll> Pll;
typedef vector<int> VI;
typedef vector<PII> VII;
//typedef pair<ll,ll>P;
#define N 200010
#define M 200010
#define INF 1e9
#define fi first
#define se second
#define MP make_pair
#define pb push_back
#define pi acos(-1)
#define mem(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(int i=(int)a;i<=(int)b;i++)
#define per(i,a,b) for(int i=(int)a;i>=(int)b;i--)
#define lowbit(x) x&(-x)
#define Rand (rand()*(1<<16)+rand())
#define id(x) ((x)<=B?(x):m-n/(x)+1)
#define ls p<<1
#define rs p<<1|1 const ll MOD=1e9+,inv2=(MOD+)/;
double eps=1e-;
int dx[]={-,,,};
int dy[]={,,-,}; int head[N],vet[N],len[N],nxt[N],dis[N],num[N][],vis[N],s,S,T,tot,n,m; int read()
{
int v=,f=;
char c=getchar();
while(c<||<c) {if(c=='-') f=-; c=getchar();}
while(<=c&&c<=) v=(v<<)+v+v+c-,c=getchar();
return v*f;
} void add(int a,int b,int c)
{
nxt[++tot]=head[a];
vet[tot]=b;
len[tot]=c;
head[a]=tot; nxt[++tot]=head[b];
vet[tot]=a;
len[tot]=;
head[b]=tot;
} bool bfs()
{
queue<int>q;
rep(i,,s) dis[i]=-;
q.push(S),dis[S]=;
while(!q.empty())
{
int u=q.front();
q.pop();
int e=head[u];
while(e)
{
int v=vet[e];
if(len[e]>&&dis[v]==-)
{
dis[v]=dis[u]+;
q.push(v);
}
e=nxt[e];
}
}
return dis[T]!=-;
} int dfs(int u,int aug)
{
if(u==T) return aug;
int e=head[u],val=,flow=;
while(e)
{
int v=vet[e];
if(len[e]>&&dis[v]==dis[u]+)
{
int t=dfs(v,min(len[e],aug));
if(!t)
{
e=nxt[e];
continue;
}
flow+=t;
aug-=t;
len[e]-=t;
len[e^]+=t;
if(!aug) break;
}
e=nxt[e];
}
if(!flow) dis[u]=-;
return flow;
} void print(int u)
{
//printf("u=%d\n",u);
if(u<=||u==S) return;
printf("%d ",u);
int e=head[u];
while(e)
{
int v=vet[e];
if(!len[e]&&v<S) print(v-n);
e=nxt[e];
}
} int main()
{
n=read(),m=read();
s=;
rep(i,,n) num[i][]=++s;
rep(i,,n) num[i][]=++s;
S=++s; T=++s;
rep(i,,s) head[i]=;
tot=;
while(m--)
{
int x=read(),y=read();
add(num[x][],num[y][],);
}
rep(i,,n) add(S,num[i][],);
rep(i,,n) add(num[i][],T,);
int ans=n;
while(bfs()) ans-=dfs(S,INF);
int e=head[T];
while(e)
{
int v=vet[e];
if(len[e])
{
e=nxt[e];
continue;
}
print(v-n);
printf("\n");
e=nxt[e];
} printf("%d\n",ans);
return ;
}
最新文章
- Bash:-:-定义空变量作为输出结合换行符\n和column输出
- [Eclipse]解决: Eclipse Maven “Add Dependency”搜索无结果
- Android --日期控件使用并显示选择的日期
- CLRS:max_heap and min_heap operation (pseudocode)
- 5个Xcode开发调试技巧
- Clean Code(三):注释
- 安卓天天练练(五)CompoundButton
- esp8266 终于装上固件了!半个月了!开始进军简单粗暴的lua语言!!
- ASP.NET Core WebApi使用Swagger生成api说明文档看这篇就够了
- ckeditor5 安装高亮,颜色插件
- ubuntu安装steam
- Fluent动网格【1】:概述
- unity插件,从一段文字中提取中文并去重
- iOS 新浪微博-5.1 首页微博列表_时间/配图
- R语言常用基础知识(入门)
- Git简明教程一、基本概念
- jqzoom插件图片放大功能的一些BUG
- POJ 1985 Cow Marathon (树形DP,树的直径)
- BestCoder Round #18(hdu5105)Math Problem(高中数学)
- 17_点击事件第四种写法_布局文件添加onclick属性