POJ 1087 A Plug for UNIX - nazgul's Blog

POJ 1087 A Plug for UNIX

nazgul posted @ 2011年2月17日 10:32 in POJ , 1400 阅读

题目大意：在一个建筑里面设有很多插座，但是每种插座只有一个。你有很多种设备，每一种设备要充电，必须插入对应的插座中，也就是有很多个插头。商店里面有很多种适配器，每种适配器一头插入一种插座里面，另外一头是另外一种插座，每种适配器的个数都是无限的。你尽量多的把设备可以同时充电，问还有几个设备无法充电。

分析：对于每种设备，如果存在对应的插座，则直接使用对应的插座。如果不存在，则用一个或多个适配器将那些不能直接用的插座转成可以使用的插座，对于某些无法转成的的设备对应的插头，则无法充电。按照这个死路，首先要记录哪些插座不能直接用，并且计算这些插座可以转换成哪些插座，还有哪些设备不能直接充电。因此插座和设备有一一对应关系，并且这些关系越多越好，由此可以想到要用二分图最大匹配。

需要注意：适配器中使用的插座或者插头，可能在建筑里面的插座以及设备插头都不相同，但是同样可以达到转换的效果，比如建筑里面有个插座类型为A，设备需要的插座为B，适配器可以通过A->C->B，这个C类型的，可能没在建筑里面的插座以及设备插头出现过。

代码如下：

100

101

102

103

104

105

106

#include <stdio.h>
#include <string.h>
#define MAXM 401
 
char rec[MAXM][25], isPlug[MAXM] = {0}, trans[MAXM][MAXM] = {0};
int iRece, iPlug, tot, iAdapt, m, n;
char path[MAXM][MAXM] = {0}, visit[MAXM];
int match[MAXM] = {0};
 
void inputReceptacles()
{
    int i;
 
    scanf( "%d", &iRece );
    for ( i = 0; i < iRece; ++i )
        scanf( "%s", rec[i] );
    tot = iRece;
}
 
int findSame( char *s, int k )
{
    int i;
 
    for ( i = 0; i < tot; ++i )
        if ( strcmp( s, rec[i] ) == 0 )
            return i;
    strcpy( rec[tot], s );
    isPlug[tot++] = k;
    return tot-1;
}
 
void inputPlug()
{
    char ch[25], s[25];
    int i, k;
 
    scanf( "%d", &iPlug );
    for ( i = 0; i < iPlug; ++i )
    {
        scanf( "%s%s", ch, s );
        k = findSame( s, 2 );
        if ( k != tot-1 ) isPlug[k]++;
    }
}
 
void inputAdapt()
{
    int i, a, b;
    char s1[250], s2[250];
 
    n = tot;
    scanf( "%d", &iAdapt );
    for ( i = 0; i < iAdapt; ++i )
    {
        scanf( "%s%s", s1, s2 );
        a = findSame( s1, 1 ); b = findSame( s2, 1 );
        trans[b][a] = 1;
    }
    for ( i = 0; i < tot; ++i )
        for ( a = 0; a < tot; ++a )
            for ( b = 0; b < tot; ++b )
                if ( trans[a][i] && trans[i][b] )
                    trans[a][b] = 1;
    for ( m = i = 0; i < n; ++i )
        if ( isPlug[i] > 1 )
        {
            for ( a = 2; a <= isPlug[i]; ++a, ++m )
            {
                for ( b = 0; b < n; ++b )
                    if ( isPlug[b] == 0 && trans[b][i] )
                        path[b][m] = 1;
            }
        }
}
 
int SearchPath( int s )
{
    for ( int i = 0; i < m; i++ )
    {
        if ( path[s][i] && !visit[i] )
        {
            visit[i] = 1;
            if ( match[i] == 0 || SearchPath( match[i] ) )
            {
                match[i] = s;
                return 1;
            }
        }
    }
    return 0;
}
 
int main()
{
    int sum, i;
 
    inputReceptacles();
    inputPlug();
    inputAdapt();
    for ( sum = i = 0; i < n; ++i )
    {
        memset( visit, 0, sizeof( visit ) );
        if ( SearchPath( i ) ) sum++;
    }
    printf( "%d\n", m-sum );
    return 0;