HDU 3315 My Brute

HDU_3315

由于要求求满足收益最大情况下改变顺序最少的方案，因此我们在建图的时候可以将权值乘以一个常数，然后对原有边的权值自加一个较小量来体现出对该边的“偏好”。

#include<stdio.h>
#include<string.h>
#define MAXD 110
#define MAX 1010
#define INF 1000000000
int V[MAXD], H[MAXD], P[MAXD], S[MAXD], X[MAXD], N;
int A[MAXD], B[MAXD], slack, visx[MAXD], visy[MAXD];
int G[MAXD][MAXD], yM[MAXD];
int check(int i, int j)
{
    if((H[i] - 1) / X[j] >= (P[j] - 1) / S[i])
        return V[i];
    else
        return -V[i];
}
int init()
{
    int i, j;
    scanf("%d", &N);
    if(N == 0)
        return 0;
    for(i = 0; i < N; i ++)
        scanf("%d", &V[i]);
    for(i = 0; i < N; i ++)
        scanf("%d", &H[i]);
    for(i = 0; i < N; i ++)
        scanf("%d", &P[i]);
    for(i = 0; i < N; i ++)
        scanf("%d", &S[i]);
    for(i = 0; i < N; i ++)
        scanf("%d", &X[i]);
    for(i = 0; i < N; i ++)
        for(j = 0; j < N; j ++)
        {
            G[i][j] = 10 * (check(i, j) + MAX);
            if(i == j)
                G[i][j] += 1;
        }
    return 1;
}
int searchpath(int u)
{
    int v, temp;
    visx[u] = 1;
    for(v = 0; v < N; v ++)
        if(!visy[v])
        {
            temp = A[u] + B[v] - G[u][v];
            if(temp == 0)
            {
                visy[v] = 1;
                if(yM[v] == -1 || searchpath(yM[v]))
                {
                    yM[v] = u;
                    return 1;
                }
            }
            else if(temp < slack)
                slack = temp;
        }
    return 0;
}
void KM()
{
    int i, j, u;
    for(i = 0; i < N; i ++)
    {
        A[i] = 0;
        for(j = 0; j < N; j ++)
            if(G[i][j] > A[i])
                A[i] = G[i][j];
    }
    memset(B, 0, sizeof(B));
    memset(yM, -1, sizeof(yM));
    for(u = 0; u < N; u ++)
        for(;;)
        {
            memset(visx, 0, sizeof(visx));
            memset(visy, 0, sizeof(visy));
            slack = INF;
            if(searchpath(u))
                break;
            for(i = 0; i < N; i ++)
            {
                if(visx[i])
                    A[i] -= slack;
                if(visy[i])
                    B[i] += slack;
            }
        }
}
void printresult()
{
    int i, res = 0, num = 0;
    for(i = 0; i < N; i ++)
    {
        if(G[yM[i]][i] % 10 != 0)
            num ++;
        res += G[yM[i]][i] / 10 - MAX;
    }
    if(res > 0)
        printf("%d %.3f%%\n", res, 100.0 * num / N);
    else
        printf("Oh, I lose my dear seaco!\n");
}
int main()
{
    while(init())
    {
        KM();
        printresult();
    }
    return 0;
}