学步园

试题安排

源程序名   arrange.???(pas|c|cpp)

输入文件名 arrange.in

输出文件名 arrange.out

时间限制   1s/testcase

空间限制   32MB

- 问题描述

给省队选拔赛命题的时候，李老师手下有N个命题人，要命N种不同类型的试题，其中每人命一题。因为每个命题人对不同题型的掌握程度不同，所以他们编出的试题难度也有不同（这用一个难度数值来表示）。为了尽可能地刁难大家，李老师决定出一张N个题的试卷，而且所有题的难度值总和最大。

- 输入数据

第一行为N(N <= 100)，代表命题人的个数。

以后N行，每行N个整数（每个数不超过100），第i行j列的数表示第i个人出的第j种题目的难度大小。

- 输出数据

一行，表示试卷难度的最大值。

- 样例输入

3

50  50  1

10  100 10

100 10  10

- 样例输出

201

评测数据下载：http://download.csdn.net/detail/yuyanggo/5384199

解法：

首先，根据样例可以知道，每个老师出的题中仅选一道（如果可以选多道或不选，那就是大水题了）。

我们可以这样理解，将原问题抽象成一个二分图，n个老师在一边，n道题在另一边，在老师 i 与题目 j 之间连边，边值为 i 号老师出的 j 号题的难度。就可以将原问题抽象成求一个二分图的最大权匹配。这种问题可以用km算法或网络流，这里我就只讲网络流的做法。

如果不会最小费用最大流的话，请先自学再来接着往下看。如果你已经会最小费用最大流的话，那么最大费用最大流想必你也可以理解了。二分图的最大权匹配，实际上就可以用最大费用最大流来做，最大费用就是最大权。

代码：

#include<cstdio>
#include<algorithm>
using namespace std;

int n,ed,map[210][210];
int dist[210],pre[210],q[210*5];
bool v[420],g[210][210];

void init()
{
  freopen("arrange.in","r",stdin);
  freopen("arrange.out","w",stdout);
}

void readdata()
{
  memset(g,0,sizeof(g));
  scanf("%d",&n);
  int i,j;
  for(i=1;i<=n;i++)
    for(j=n+1;j<=n+n;j++)
      scanf("%d",&map[i][j]),map[j][i]=-map[i][j],g[i][j]=1;
          
  for(i=1;i<=n;i++)map[0][i]=map[i][0]=0,g[0][i]=1;
  for(i=n+1,ed=n*2+1;i<ed;i++)map[i][ed]=map[ed][i]=0,g[i][ed]=1;    
}

inline bool spfa()
{
  memset(dist,-20,sizeof(dist));
  memset(pre,-1,sizeof(pre));
  memset(v,0,sizeof(v));
  int l=1,r=1,k,i;    
  q[1]=0,v[0]=1,dist[0]=0;
  while(l<=r)
    {
      k=q[l];l++;
      for(i=1;i<=ed;i++)
        if(g[k][i] && dist[i]<dist[k]+map[k][i])
          {
            dist[i]=dist[k]+map[k][i];
            pre[i]=k;
            if(!v[i])q[++r]=i,v[i]=1;
          }
      v[k]=0;
    }
  if(dist[ed]==dist[209])return 0;
  return 1;  
}

void work()
{
  int maxcost=0,k;
  while(spfa())
    {
      maxcost+=dist[ed];
      for(k=ed;pre[k]!=-1;k=pre[k])
        g[pre[k]][k]-=1,g[k][pre[k]]+=1;
    }
  printf("%d\n",maxcost);  
}

int main()
{
  init();
  readdata();
  work();
  return 0;
}