Machine Schedule 赤裸裸的二分匹配 二部图中的点覆盖书==匹配数
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #include <string> 7 #include <vector> 8 #include <set> 9 #include <map> 10 #include <stack> 11 #include <queue> 12 #include <sstream> 13 #include <iomanip> 14 using namespace std; 15 typedef long long LL; 16 const int INF = 0x4fffffff; 17 const double EXP = 1e-5; 18 const int MS = 105; 19 const int SIZE = 100005; 20 21 // data struct 22 int edges[MS][MS]; 23 int cx[MS],cy[MS]; 24 int mark[MS]; 25 26 int n,m,k; 27 28 int path(int u) 29 { 30 for(int v=1;v<m;v++) 31 { 32 if(edges[u][v]&&!mark[v]) 33 { 34 mark[v]=1; 35 if(cy[v]==-1||path(cy[v])) 36 { 37 cx[u]=v; 38 cy[v]=u; 39 return 1; 40 } 41 } 42 } 43 return 0; 44 } 45 46 void match() 47 { 48 int ans=0; 49 memset(cx,0xff,sizeof(cx)); 50 memset(cy,0xff,sizeof(cy)); 51 for(int u=1;u<n;u++) 52 { 53 if(cx[u]==-1) 54 { 55 memset(mark,0,sizeof(mark)); 56 ans+=path(u); 57 } 58 } 59 printf("%d\n",ans); 60 } 61 62 63 int main() 64 { 65 while(scanf("%d",&n)&&n) 66 { 67 scanf("%d%d",&m,&k); 68 memset(edges,0,sizeof(edges)); 69 int t,u,v; 70 for(int i=0;i<k;i++) 71 { 72 scanf("%d%d%d",&t,&u,&v); 73 if(u!=0&&v!=0) 74 { 75 edges[u][v]=1; 76 } 77 } 78 match(); 79 } 80 return 0; 81 }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。