首页 > 代码库 > 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-二分图匹配