思路
抽象为二分图模型,注意左右两边的0点应该从二分图中删去
要求最少转换模式的次数,就是在求二分图的最小点集覆盖,即求二分图的最大匹配
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 104;
int n,m,k,ans,v[N],f[N];
vector<int>e[N];
int dfs(int x){
for(int i = 0;i < e[x].size();i++){
int y = e[x][i];
if(!v[y]){
v[y] = 1;
if(f[y] == - 1 || dfs(f[y])){
f[y] = x;
return 1;
}
}
}
return 0;
}
void MS(){
cin>>m>>k;
for(int i = 0;i < n;i++)e[i].clear();
while(k--){
int x,y,z;
cin>>z>>x>>y;
if(x && y)e[x].push_back(y);
}
ans = 0;
memset(f,-1,sizeof(f));
for(int i = 0;i < n;i++){
memset(v,0,sizeof(v));
ans += dfs(i);
}
cout<<ans<<endl;
}
int main(){
while(cin>>n && n)MS();
}