POJ 1422 SSL-1340最小経路カバー【図の最大マッチング】
リンク
http://poj.org/problem?id=1422
大意
tグループのデータがあります.各グループのデータはn個の点を与えられます.m m m本の辺の方向図があります.最小経路のカバーを求めます.
考え方
ハンガリーのアルゴリズムは、1つの公式によると、最小経路カバー数=原図Gの頂点数-2分図の最大マッチング数
コード
http://poj.org/problem?id=1422
大意
tグループのデータがあります.各グループのデータはn個の点を与えられます.m m m本の辺の方向図があります.最小経路のカバーを求めます.
考え方
ハンガリーのアルゴリズムは、1つの公式によると、最小経路カバー数=原図Gの頂点数-2分図の最大マッチング数
コード
#include
#include
#define N 121
#define M 10121
#define LL long long
#define r(i,a,b) for(int i=a;i<=b;i++)
#define zero(a) memset(a,0,sizeof(a))
using namespace std;
struct node{int next,to;}edge[M];int l[M],tot,x,y,n,m,q,link[N],ans,t;bool vis[N];
void add(int u,int v){edge[++tot].to=v;edge[tot].next=l[u];l[u]=tot;}
LL read()//
{
char c;int f=0,d=1;
while((c=getchar())<48||c>57)if(c=='-')d=-1;f=(f<<3)+(f<<1)+c-48;
while((c=getchar())>=48&&c<=57)f=(f<<3)+(f<<1)+c-48;
return d*f;
}
bool find(int p)//
{
for(int i=l[p];i;i=edge[i].next)
if(!vis[edge[i].to])
{
vis[edge[i].to]=1;
q=link[edge[i].to];
link[edge[i].to]=p;
if(!q||find(q)) return true;
link[edge[i].to]=q;
}
return false;
}
int main()
{
t=read();
while(t--)
{
tot=0;zero(l);zero(link);//
n=read();m=read();
r(i,1,m) add(read(),read());ans=0;// +
r(i,1,n)
{
zero(vis);
ans+=find(i);//
}
printf("%d
",n-ans);//
}
}