poj 1087 A Plug for UNIX(最大流)

解题思路

题意：

       房间里有n个不同的插座，每种插座只有一个；有m种不同的电器要插在不同的插座上，还有k种适配器，每种的数量是无限的。求的是有多少种电器没插座可插。

 

思路：

又是最大流，建图：

       每个电器和对应的插座或适配器连接，权为1，适配器之间连接时权为无穷大，再加一个源点连接所有电器，权为1，加一个汇点连接所有插座，权为1.

       然后用SAP算最大流flow，最后用电器的总数减去flow得解。

       数组要开到400以上，因为有100个插座，100个电器，100个适配器，而适配器两端又可能全部都跟那100个插座不同的。所以一共是400。

源程序

 

#include <stdio.h>
#include <string.h>
#include <queue>
#include <conio.h>
using namespace std;
#define N 500
#define M 50
#define inf 100000000
int g[N][N], pre[N], num[N], d[N];
int n;

int find(char s[][M], int n, char key[M])
{
    int i;
    for(i=1; i<=n; i++)
    {
        if(strcmp(s[i], key) == 0)
            return i;
    }
    return -1;
}

int findp(int i)
{
    int j;
    for(j=1; j<=n; j++)
    {
        if(g[i][j] > 0 && d[i] == d[j] + 1)
            return j;
    }
    return -1;
}

int relable(int i)
{
    int j, mm;
    mm = inf;
    for(j=1; j<=n; j++)
    {
        if(g[i][j] > 0)
        {
            mm = min(mm, d[j] + 1);
        }
    }
    return mm == inf ? n : mm;
}


int maxflow(int s, int t)
{
    int i, j, k, x, flow;

    i = s;
    flow = 0;
    while(d[s] < n)
    {
        j = findp(i);
        if(j != -1)
        {
            pre[j] = i;
            i = j;
            if( i == t)
            {
                x = inf;
                for(k = t; k != s; k=pre[k])
                {
                    x = min(x, g[pre[k]][k]);
                }
                for(k=t; k !=s; k=pre[k])
                {
                    g[pre[k]][k] -= x;
                    g[k][pre[k]] += x;
                }
                flow += x;
                i = s;
            }
        }
        else
        {
            x = relable(i);
            num[x]++;
            num[d[i]]--;
            if(num[d[i]] == 0)
                return flow;
            d[i] = x;
            if(i != s)
                i = s;
        }
    }
    return flow;
}


int main()
{
    int i, j, k;
    int index1, index2;
    int recno, devno, adpno;
    int re[N];
    char temp1[M], temp2[M];
    char dev[N][M], rec[N][M];;

    freopen("in.txt", "r", stdin);

    scanf("%d", &recno); //插座

    k = recno;
    for(i=1; i<=recno; i++)
    {
        scanf("%s", rec[i]);
    }

    scanf("%d", &devno); //插头


    for(i=1; i<=devno; i++)
    {
        scanf("%s%s", dev[i], temp1);
        re[i] = find(rec, recno, temp1);
        if(re[i] < 0)
        {
            recno++;
            re[i] =recno;
            strcpy(rec[recno], temp1);
        }
    }
    n = recno + devno;
    for(i=1; i<=devno; i++)
    {
        g[i][devno+re[i]] = 1;
        g[n+1][i] = 1;
    }
    
    for(i=1; i<=k; i++)
    {
        g[i+devno][n+2] = 1;
    }

    scanf("%d", &adpno); //适配器

    for(i=1; i<=adpno; i++)
    {
        scanf("%s%s", temp1, temp2);
        index1 = find(rec, recno, temp1);
        index2 = find(rec, recno, temp2);
        g[index1+devno][index2+devno] = inf;
    }
    n = n+2;
    memset(d, 0, sizeof(d));
    printf("%d\n", devno - maxflow(n-1, n));
    getch();
    return 0;
}

memory：808K  time： 16MS