Hdu 3395 【最大权值匹配】.cpp-白红宇

Hdu 3395 【最大权值匹配】.cpp

阅读量：4616 次

发布时间：2019-06-09

本文共 2987 字，大约阅读时间需要 9 分钟。

题意：

有一种奇怪的小鱼..

他会攻击他认为是女的鱼..<如果她自己也是女的呢？不懂..果然是奇怪的小鱼..>

然后生下来的孩子的值等于父母值的异或结果..<更奇怪了..囧~>

问最可能得到的孩子值最大是多少~

输入：

　　一个n代表有n条鱼

　　接下来1行有n个数表示第i条鱼的值

　　然后n*n行~表示第i行的鱼认为第j行的鱼是女的鱼

思路：

　　根据给出的n*n矩阵~

　　得出第i个点对应第j个点..即ij连边的值wij..

　　然后转化为求最佳匹配<最大边权匹配>

Tips：

　　读入数据的时候要以字符串的形式..

　　坦白说我到现在都没理解一个一个字符读的话为什么会wa..

　　求解..

　　传说.. 是因为windows系统换行符是两个字符..

　　所以一个getchar()就会错~

　　以后都用字符串处理吧..

Code：

View Code

1 #include 
       
          2 #include 
        
           3 #include 
         
            4 #include 
          
             5 using namespace std;  6 #define clr(x) memset(x, 0, sizeof(x))  7 #define M 210  8 const int INF = 0x1f1f1f1f;  9  10 int v; 11 int link[M], lx[M], ly[M]; 12 int visx[M], visy[M], G[M][M]; 13 int slack; 14 int DFS(int x) 15 { 16     visx[x] = 1; 17     for (int y = 1; y <= v; ++y) 18     { 19         if (visy[y]) 20             continue; 21         int t = lx[x] + ly[y] - G[x][y]; 22         if (t == 0) 23         { 24             visy[y] = 1; 25             if (link[y] == -1||DFS(link[y])) 26             { 27                 link[y] = x; 28                 return 1; 29             } 30         } 31         else if (slack > t) 32             slack = t; 33     } 34     return 0; 35 } 36  37 int KM() 38 { 39     int i,j; 40     memset (link,-1,sizeof(link)); 41     memset (ly,0,sizeof(ly)); 42     for (i = 1;i <= v; ++i) 43         for (j = 1,lx[i] = -INF;j <= v; ++j) 44             if (G[i][j] > lx[i]) 45                 lx[i] = G[i][j]; 46  47     for (int x = 1;x <= v; ++x) 48     { 49         memset(visx,0,sizeof(visx)); 50         memset(visy,0,sizeof(visy)); 51         while (1) 52         { 53             slack=INF; 54             if (DFS(x)) 55                 break; 56             for(i = 1; i <= v; i++) 57             { 58                 if(visx[i]) {  lx[i]-=slack;  visx[i]=0;  } 59                 if(visy[i]) {  ly[i]+=slack;  visy[i]=0;  } 60             } 61  62         } 63     } 64     int res = 0; 65     for (i = 1;i <= v; ++i) 66             res += G[link[i]][i]; 67     return res; 68 } 69  70  71 int main() 72 { 73     int i, j, k; 74     int n, val[110]; 75     char w[110]; 76     while(scanf("%d", &n) != EOF) 77     { 78         if(n == 0) break; 79         clr(G); 80         v = n; 81  82         for(i = 1; i <= n; ++i) 83         scanf("%d", &val[i]); 84  85 /* 86         for(i = 1; i <= n; ++i) { 87             getchar(); 88             for(j = 1; j <= n; ++j) { 89                 scanf("%c", &w); 90                 if(w == '1') G[i][j] = val[i]^val[j]; 91             } 92         } 93 */ 94  95         for(i = 1; i <= n; ++i) { 96             scanf("%s", w+1); 97             for(j = 1; j <= n; ++j) 98                 if(w[j]-'0') G[i][j] = val[i]^val[j]; 99         }100 101         int ans = KM();102         printf("%d\n", ans);103     }104     return 0;105 }