首页 > ACM题库 > HDU-杭电 > HDU 2853-Assignment-二分图-[解题报告]HOJ
2014
02-17

HDU 2853-Assignment-二分图-[解题报告]HOJ

Assignment

问题描述 :

Last year a terrible earthquake attacked Sichuan province. About 300,000 PLA soldiers attended the rescue, also ALPCs. Our mission is to solve difficulty problems to optimization the assignment of troops. The assignment is measure by efficiency, which is an integer, and the larger the better.
We have N companies of troops and M missions, M>=N. One company can get only one mission. One mission can be assigned to only one company. If company i takes mission j, we can get efficiency Eij.
We have a assignment plan already, and now we want to change some companies’ missions to make the total efficiency larger. And also we want to change as less companies as possible.

输入:

For each test case, the first line contains two numbers N and M. N lines follow. Each contains M integers, representing Eij. The next line contains N integers. The first one represents the mission number that company 1 takes, and so on.
1<=N<=M<=50, 1<Eij<=10000.
Your program should process to the end of file.

输出:

For each test case, the first line contains two numbers N and M. N lines follow. Each contains M integers, representing Eij. The next line contains N integers. The first one represents the mission number that company 1 takes, and so on.
1<=N<=M<=50, 1<Eij<=10000.
Your program should process to the end of file.

样例输入:

3 3
2 1 3
3 2 4
1 26 2
2 1 3
2 3
1 2 3
1 2 3
1 2

样例输出:

2 26
1 2

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
#include <cmath>
#include <cstdlib>
#define L(rt) (rt<<1)
#define R(rt) (rt<<1|1)
#define ll long long
#define eps 1e-6
using namespace std;

const int maxn=55;
const int INF=1000000000;
int G[maxn][maxn],lx[maxn],match[maxn],ly[maxn],slack[maxn];
bool visx[maxn],visy[maxn];
int n,m;
bool find(int u)
{
    visx[u]=true;
    for(int i=1; i<=m; i++)
    {
        if(visy[i]) continue;
        if(lx[u]+ly[i]==G[u][i])
        {
            visy[i]=true;
            if(match[i]==-1||find(match[i]))
            {
                match[i]=u;
                return true;
            }
        }
        else slack[i]=min(slack[i],lx[u]+ly[i]-G[u][i]);
    }
    return false;
}
void KM()
{
    memset(match,-1,sizeof(match));
    for(int i=1; i<=n; i++) lx[i]=-INF;
    memset(ly,0,sizeof(ly));
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            lx[i]=max(lx[i],G[i][j]);
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++) slack[j]=INF;
        while(1)
        {
            memset(visx,false,sizeof(visx));
            memset(visy,false,sizeof(visy));
            if(find(i)) break;
            else
            {
                int temp=INF;
                for(int j=1; j<=m; j++)
                    if(!visy[j]&&temp>slack[j]) temp=slack[j];
                for(int j=1; j<=n; j++)
                    if(visx[j]) lx[j]-=temp;
                for(int j=1; j<=m; j++)
                {
                    if(visy[j]) ly[j]+=temp;
                    else slack[j]-=temp;
                }
            }
        }
    }
}
int main()
{
    int a;
    while(~scanf("%d%d",&n,&m))
    {
        for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&G[i][j]);
            G[i][j]*=100;
        }
        int tot=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a);
            tot+=G[i][a];
            G[i][a]++;
        }
        KM();
        int sum=0;
        for(int i=1; i<=m; i++)
        if(match[i]!=-1) sum+=G[match[i]][i];
        printf("%d %d\n",n-sum%100,sum/100-tot/100);
    }
    return 0;
}

解题参考:http://blog.csdn.net/weyuli/article/details/11269473


  1. /*
    * =====================================================================================
    *
    * Filename: 1366.cc
    *
    * Description:
    *
    * Version: 1.0
    * Created: 2014年01月06日 14时52分14秒
    * Revision: none
    * Compiler: gcc
    *
    * Author: Wenxian Ni (Hello World~), niwenxianq@qq.com
    * Organization: AMS/ICT
    *
    * =====================================================================================
    */

    #include
    #include

    using namespace std;

    int main()
    {
    stack st;
    int n,i,j;
    int test;
    int a[100001];
    int b[100001];
    while(cin>>n)
    {
    for(i=1;i>a[i];
    for(i=1;i>b[i];
    //st.clear();
    while(!st.empty())
    st.pop();
    i = 1;
    j = 1;

    while(in)
    break;
    }
    while(!st.empty()&&st.top()==b[j])
    {
    st.pop();
    j++;
    }
    }
    if(st.empty())
    cout<<"YES"<<endl;
    else
    cout<<"NO"<<endl;
    }
    return 0;
    }