[cpp]
/*
題意：有個城鎮，所有路都是單行道，並且沒有環，所有路都連接在十字路口上
現在用最少的傘兵走完這些式子路口，每個只能走一遍
很明顯的最小路徑覆蓋
最小路徑覆蓋=點數-最大匹配
需要拆點 所有式子路口 在X中一個 在Y中一個
路把兩個集合中十字路口連接起來
求最大匹配 還是匈牙利
*/
#include<stdio.h>
#include<vector>
using namespace std;
vector<int>v[150];
int t,n,m;
int match[150],vis[150];//都只是對Y集中的點
int dfs(int i)
{
for(int j=0;j<v[i].size();++j)
{
if(!vis[v[i][j]])
{
vis[v[i][j]]=1;
if(match[v[i][j]]==-1||dfs(match[v[i][j]]))
{
match[v[i][j]]=i;
return 1;
}
}
}
return 0;
}
int main()
{
int i,a,b;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
for(i=0;i<=n;i++)
v[i].clear();
for(i=1;i<=m;++i)
{
scanf("%d%d",&a,&b);
v[a].push_back(b);
}
a=0;////
memset(match,-1,sizeof(match));
for(i=1;i<=n;i++)
{
memset(vis,0,sizeof(vis));
if(dfs(i))
a++;
}////
printf("%d\n",n-a);//最小路徑覆蓋=點數-最大匹配
}
return 0;
}
/*
題意：有個城鎮，所有路都是單行道，並且沒有環，所有路都連接在十字路口上
現在用最少的傘兵走完這些式子路口，每個只能走一遍
很明顯的最小路徑覆蓋
最小路徑覆蓋=點數-最大匹配
需要拆點 所有式子路口 在X中一個 在Y中一個
路把兩個集合中十字路口連接起來
求最大匹配 還是匈牙利
*/
#include<stdio.h>
#include<vector>
using namespace std;
vector<int>v[150];
int t,n,m;
int match[150],vis[150];//都只是對Y集中的點
int dfs(int i)
{
for(int j=0;j<v[i].size();++j)
{
if(!vis[v[i][j]])
{
vis[v[i][j]]=1;
if(match[v[i][j]]==-1||dfs(match[v[i][j]]))
{
match[v[i][j]]=i;
return 1;
}
}
}
return 0;
}
int main()
{
int i,a,b;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
for(i=0;i<=n;i++)
v[i].clear();
for(i=1;i<=m;++i)
{
scanf("%d%d",&a,&b);
v[a].push_back(b);
}
a=0;////
memset(match,-1,sizeof(match));
for(i=1;i<=n;i++)
{
memset(vis,0,sizeof(vis));
if(dfs(i))
a++;
}////
printf("%d\n",n-a);//最小路徑覆蓋=點數-最大匹配
}
return 0;
}
