“亚信科技杯”南邮第七届大学生程序设计竞赛之网络预赛 A noj 2073 FFF [ 二分图最大权匹配 || 最大费用最大流 ]

FFF

时间限制(普通/Java) : 1000 MS/ 3000 MS 运行内存限制 : 65536 KByte
总提交 : 145 测试通过 : 13

题目描述

FFF团，一个异端审判组织，团员活跃在各个角落，每当烧烤节来临的时候，我们都能听到他们传播的那熟悉的旋律：

烧啊~烧啊~烧啊烧啊烧~ (请自行脑补《当》)

FFF团成员自带这样一个属性：凭空变出火把与汽油，两者配合起来才能让FFF之火duang的一下烧起来，但是不同的火把与不同的汽油配合产生的火焰是不同的，现在有n种火把与n种汽油，已知每一种火把与每一种汽油配合时产生的火焰的旺盛程度，现在求怎样使得火把与汽油一一配对，产生最旺盛的火焰。

输入

第一行为一个整数T，表示有T组数据

每组数据第一行为一个正整数n（2≤n≤30）

第二行开始一共有n行，每行为n个正整数，第i行第j个数表示第i种火把与第j种汽油配合的火焰的旺盛程度。(0<a[i][j]≤10000)

输出

每组数据输出一个整数，表示最大的火焰旺盛程度

样例输入

2
3
5 2 6
6 7 9
7 4 1
4
8 5 2 8
5 8 2 1
9 6 3 7
7 5 8 1

样例输出

20
33

题目来源

kojimai

转一发wdd的题解：

http://blog.csdn.net/u010535824/article/details/44746223

A：一对一配对，两种解法，一种是用二分最大权匹配 km算法可解，二是用最大费用最大流，两种都是直接套算法的模板就可以了。

下面给出km的做法

njczy2010	2073	Accepted	0MS	212K	2522Byte	G++	2015-04-01 17:14:34.0

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <stack>
  4 #include <vector>
  5 #include <algorithm>
  6 #include <map>
  7 #include <string>
  8 #include <queue>
  9 #include <cmath>
 10 
 11 #define ll long long
 12 int const N = 35;
 13 int const M = 100005;
 14 int const INF = 0x3f3f3f3f;
 15 ll const mod = 1000000007;
 16 
 17 using namespace std;
 18 
 19 int T;
 20 int n;
 21 int nx,ny;       //两边的点数
 22 int g[N][N];    //二分图描述
 23 int linker[N],lx[N],ly[N];      //y中各点匹配状态，x,y中的点标号
 24 int slack[N];
 25 bool visx[N],visy[N];
 26 
 27 bool DFS(int x)
 28 {
 29     visx[x] = true;
 30     for(int y = 0;y < ny;y++)
 31     {
 32         if(visy[y]) continue;
 33         int tmp = lx[x] + ly[y] -g[x][y];
 34         if(tmp == 0)
 35         {
 36             visy[y] = true;
 37             if(linker[y] == -1 || DFS(linker[y]))
 38             {
 39                 linker[y] = x;
 40                 return true;
 41             }
 42         }
 43         else if(slack[y] > tmp)
 44             slack[y] = tmp;
 45     }
 46     return false;
 47 }
 48 
 49 int KM()
 50 {
 51     memset(linker,-1,sizeof(linker));
 52     memset(ly,0,sizeof(ly));
 53     for(int i = 0;i < nx;i++)
 54     {
 55         lx[i] = -INF;
 56         for(int j = 0;j < ny;j++)
 57             if(g[i][j] > lx[i])
 58                 lx[i] = g[i][j];
 59     }
 60     for(int x =0;x < nx;x++)
 61     {
 62         for(int i = 0;i < ny ;i++)
 63             slack[i] = INF;
 64         while(true)
 65         {
 66             memset(visx,false,sizeof(visx));
 67             memset(visy,false,sizeof(visy));
 68             if(DFS(x)) break;
 69             int d = INF;
 70             for(int i = 0;i < ny;i++)
 71                 if(!visy[i] && d > slack[i])
 72                     d = slack[i];
 73             for(int i = 0 ; i < nx ;i++)
 74                 if(visx[i])
 75                     lx[i] -= d;
 76             for(int i = 0 ; i < ny ;i++)
 77             {
 78                 if(visy[i]) ly[i] += d;
 79                 else slack[i] -= d;
 80             }
 81         }
 82     }
 83     int res = 0;
 84     for(int i = 0;i < ny ;i++)
 85         if(linker[i] != -1)
 86             res += g[ linker[i] ][i];
 87     return res;
 88 }
 89 
 90 void ini()
 91 {
 92     scanf("%d",&n);
 93     int i,j;
 94     for(i = 0;i < n;i++){
 95         for(j = 0;j < n;j++)
 96             scanf("%d",&g[i][j]);
 97     }
 98     nx = ny =n;
 99 }
100 
101 void solve()
102 {
103 
104 }
105 
106 void out()
107 {
108     printf("%d
",KM());
109 }
110 
111 int main()
112 {
113     //freopen("data.in","r",stdin);
114     //freopen("data.out","w",stdout);
115     scanf("%d",&T);
116     //for(int cnt=1;cnt<=T;cnt++)
117     while(T--)
118     //while(scanf("%d%d%d",&a,&b,&n)!=EOF)
119     {
120         ini();
121         solve();
122         out();
123     }
124 }