【codevs1904】[网络流24题]最小路径覆盖问题

2019-11-08 03:00:31

字体：大中小

来源：转载

供稿：网友

拆点，转化成二分图，直接代konig定理. 最小路径覆盖数 = 顶点数 - 最大匹配数因为匈牙利好写写的匈牙利.

#include<iostream>#include<cstdio>#include<cstring>#include<string>#include<algorithm>using namespace std;const int N=100010;int matching[N],te,check[N],ans,head[N],n,m;struct edge{ int v,next;}e[200010];void add(int u,int v){ e[++te].v=v; e[te].next=head[u]; head[u]=te;}int dfs(int u){ for (int i=head[u];i;i=e[i].next) { int v=e[i].v; if (!check[v]) { check[v]=1; if (matching[v]==-1||dfs(matching[v])) { matching[u]=v; matching[v]=u; return true; } } } return false;}int hungarian(){ memset(matching,-1,sizeof(matching)); for (int i=1;i<=n;i++) { if (matching[i]==-1) { memset(check,0,sizeof(check)); if(dfs(i))++ans; } }}int main(){ ans=0; memset(head,0,sizeof(head)); cin>>n>>m; for (int i=1;i<=m;++i) { int u,v; scanf("%d%d",&u,&v); add(u,v+n); } hungarian(); cout<<n-ans;}

上一篇：Linux中task_struct结构体字段分析

下一篇：设计模式-工厂模式