首页 > 代码库 > HDU2819-Swap-二分图匹配
HDU2819-Swap-二分图匹配
把矩阵上的1建成边,把边建成点
然后跑一个二分图匹配,就找到了主对角线的元素,之后排个序就可以了
1 /*--------------------------------------------------------------------------------------*/ 2 3 #include <algorithm> 4 #include <iostream> 5 #include <cstring> 6 #include <ctype.h> 7 #include <cstdlib> 8 #include <cstdio> 9 #include <vector> 10 #include <string> 11 #include <queue> 12 #include <stack> 13 #include <cmath> 14 #include <set> 15 #include <map> 16 17 //debug function for a N*M array 18 #define debug_map(N,M,G) printf("\n");for(int i=0;i<(N);i++) 19 {for(int j=0;j<(M);j++){ 20 printf("%d",G[i][j]);}printf("\n");} 21 //debug function for int,float,double,etc. 22 #define debug_var(X) cout<<#X"="<<X<<endl; 23 #define LL long long 24 const int INF = 0x3f3f3f3f; 25 const LL LLINF = 0x3f3f3f3f3f3f3f3f; 26 /*--------------------------------------------------------------------------------------*/ 27 using namespace std; 28 29 int N,M,T; 30 const int maxn = 210; 31 const int maxm = 10010; 32 33 struct Edge{ 34 int to,next; 35 }edge[maxm]; 36 int head[maxn],tot; 37 void init() 38 { 39 tot = 0; 40 memset(head,-1,sizeof head); 41 } 42 void add_edge(int u,int v) 43 { 44 edge[tot].to = v;edge[tot].next = head[u]; 45 head[u] = tot++; 46 } 47 48 int linker[maxn]; 49 bool used[maxn]; 50 int uN; 51 52 bool dfs(int u) 53 { 54 for(int i=head[u];~i;i =edge[i].next) 55 { 56 int v = edge[i].to; 57 if(!used[v]) 58 { 59 used[v] = true; 60 if(linker[v] == -1 || dfs(linker[v])) 61 { 62 linker[v] = u; 63 return true; 64 } 65 } 66 } 67 return false; 68 } 69 70 int hungary() 71 { 72 int res = 0; 73 memset(linker,-1,sizeof linker); 74 for(int u=1;u<=uN;u++) 75 { 76 memset(used,false,sizeof used); 77 if(dfs(u)) res++; 78 } 79 return res/2; 80 } 81 vector <pair<int,int> > op; 82 int save[maxn]; 83 84 bool ok() 85 { 86 for(int i=1;i<=N;i++) if(save[i] != i) return false; 87 return true; 88 } 89 90 int main() 91 { 92 while(~scanf("%d",&N)) 93 { 94 uN = 2*N; 95 init(); 96 for(int i=1;i<=N;i++) 97 { 98 for(int j=1,tmp;j<=N;j++) 99 {100 scanf("%d",&tmp);101 if(tmp == 1)102 {103 add_edge(i,j+N);104 add_edge(j+N,i);105 }106 }107 }108 int match = hungary();109 if(match < N)110 {111 printf("-1\n");112 }113 else114 {115 for(int u=1;u<=N;u++)116 {117 int v = linker[u] - N;118 //printf("[%d,%d]\n",u,v);119 save[u] = v;120 }121 op.clear();122 while(!ok())123 {124 for(int i=1;i<=N;i++)125 {126 if(save[i] != i)127 {128 op.push_back(make_pair(i,save[i]));129 swap(save[i],save[save[i]]);130 }131 }132 }133 printf("%d\n",op.size());134 for(int i=0;i<op.size();i++)135 {136 printf("R %d %d\n",op[i].first,op[i].second);137 }138 }139 }140 }
HDU2819-Swap-二分图匹配
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。