东莞贸易网站建设,公司网站推广费用,微信推广平台自己可以做,做国外衣服的网站有哪些题目链接#xff1a;http://poj.org/problem?id1325 题意#xff1a;A机器有n个模式#xff0c;B机器有m个模式#xff0c;有k个任务#xff0c;第i个任务可以用A机器的ai模式或者B机器的bi模式#xff0c;换模式需要重启#xff0c;开始两个机器都在模式0#xff0c;…题目链接http://poj.org/problem?id1325 题意A机器有n个模式B机器有m个模式有k个任务第i个任务可以用A机器的ai模式或者B机器的bi模式换模式需要重启开始两个机器都在模式0问最少需要重启几次。分析要求最小的重启次数也就是求出除了0模式最少要工作在几个模式建图A的模式为X集B的模式为Y集每个任务看做一条线连接X集和Y集则问题转化为求X、Y中最少的点使得每条线至少有一个端点被选。即最小点集覆盖。根据最小点集覆盖二分图最大匹配。 代码 1 #include iostream 2 #include cstring 3 #include cstdio 4 using namespace std; 5 const int N1001; 6 int map[N][N],vis[N],link[N]; 7 int n1,n2,k; 8 int find(int x) 9 {10 int i;11 for(i1;in2;i)12 {13 if(map[x][i]!vis[i])14 {15 vis[i]1;16 if(!link[i]||find(link[i]))17 {18 link[i]x;19 return 1;20 }21 }22 }23 return 0;24 }25 int main()26 {27 int a,b,c,i,sum;28 while(~scanf(%d,n1))29 {30 if(!n1)31 break;32 scanf(%d%d,n2,k);33 sum0;34 memset(map,0,sizeof(map));35 memset(link,0,sizeof(link));36 while(k--)37 {38 scanf(%d%d%d,a,b,c);39 if(b*c)40 map[b][c]1;41 }42 for(i1;in1;i)43 {44 memset(vis,0,sizeof(vis));45 if(find(i))46 sum;47 }48 printf(%d\n,sum);49 }50 return 0;51 } 转载于:https://www.cnblogs.com/pony1993/archive/2012/08/13/2636916.html
