C - A Plug for UNIX - poj 1087(最大流)

题目大意:这个题意有些蛋疼,看了很大会才明白什么意思,有N个插座,这些插座都是有类型的只能给这种类型的电器充电,下面接着给了M种电器,和电器的插头类型,还有K种转换器,可以把一种类型转换成另一种,转换器也是可以串联使用的。

C - A Plug for UNIX - poj 1087(最大流)

输入说明:
首先输入的是一个N,下面有N种插座,每种插座都有一个字符串代表,接着输入一个M,表示有M个电器需要充电,输入的每行有一个电器和它需要的插座类型,然后输入一个K,下面有K个转换器。
分析:这个英文写的这么长确实比较难理解,不过看懂题意后也是比较容易了,可以让电器给可以匹配的插座或者转换器连接,然后让转换器的给别的转换器或者插座连接,虚拟一个源点和所有的手机连接,在虚拟一个汇点让所有的插座与它相连,建图估计有些麻烦.
注意:转换器是无限提供的.......
*********************************************************************************************************************
#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std; const int MAXN = ;
const int oo = 1e9+; int G[MAXN][MAXN], layer[MAXN];
char s[MAXN][]; bool canLine(char s1[], char s2[])///判断转接口是否相同
{
    if(strcmp(s1, s2) == )
        return true;
    return false;
}
bool bfs(int start, int End)
{
    bool used[MAXN] = {};
    queue<int> Q; Q.push(start);
    memset(layer, -, sizeof(layer));
    layer[start] = , used[start] = true;     while(Q.size())
    {
        int u = Q.front();Q.pop();         if(u == End)return true;         for(int i=; i<=End; i++)
        {
            if(G[u][i] && used[i] == false)
            {
                used[i] = true;
                layer[i] = layer[u] + ;
                Q.push(i);
            }
        }
    }     return false;
}
int dfs(int u, int MaxFlow, int End)
{
    if(u == End)return MaxFlow;     int uFlow = ;     for(int i=; i<=End; i++)
    {
        if(G[u][i] && layer[i] == layer[u]+)
        {
            int flow = min(MaxFlow-uFlow, G[u][i]);
            flow = dfs(i, flow, End);             G[u][i] -= flow;
            G[i][u] += flow;             uFlow += flow;             if(uFlow == MaxFlow)
                break;
        }
    }     return uFlow;
}
int dinic(int start, int End)
{
    int MaxFlow = ;     while( bfs(start, End) == true )
        MaxFlow += dfs(start, oo, End);     return MaxFlow;
} int main()
{
    int N, M, K;     while(scanf("%d", &N) != EOF)
    {
        int i, j;         memset(G, , sizeof(G));         for(i=; i<=N; i++)///插头从1~N
            scanf("%s", s[i]);         scanf("%d", &M);
        for(i=; i<=M; i++)///手机从N~N+M,忽略手机名字
            scanf("%*s%s", s[i+N]);         scanf("%d", &K);
        ///Ki是转换头进入的开始点,Kj是转换头出去的开始点,start是源点,End是汇点
        int Ki = N+M, Kj = Ki+K, start = Kj+K+, End = start+;
        for(i=; i<=K; i++)///转换器的进入从N+M~N+M+K,转换器的出从N+M+K~N+M+2*K
        {///把入和出连接
            scanf("%s%s", s[Ki+i], s[Kj+i]);
            G[Ki+i][Kj+i] = oo;///转换器无限提供
        }         for(i=; i<=M; i++)
        {///建立手机和转换器,插座的关系
            for(j=; j<=N; j++)
            {///匹配一下手机和插座是否直接可以相连
                if( canLine(s[i+N], s[j]) == true)
                    G[i+N][j] = true;
            }
            for(j=; j<=K; j++)
            {///匹配一下手机和转换器入是否可以相连
                if( canLine(s[i+N], s[Ki+j]) == true)
                    G[i+N][Ki+j] = true;
            }
        }         for(i=; i<=K; i++)
        {///建立转换器与转换器或者插座的关系
            for(j=; j<=K; j++)
            {///匹配转换器出与转换器入,转换器无限提供,直接最大值
                if(i!=j && canLine(s[Kj+i], s[Ki+j]) == true)
                    G[Kj+i][Ki+j] = oo;
            }
            for(j=; j<=N; j++)
            {///匹配转换器出和插座的关系
                if(canLine(s[Kj+i], s[j]) == true)
                    G[Kj+i][j] = true;
            }
        }         for(i=; i<=M; i++)
        {///源点与手机的关系
            G[start][N+i] = true;
        }
        for(i=; i<=N; i++)
        {///插座与汇点的关系
            G[i][End] = true;
        }         printf("%d\n", M-dinic(start, End));
    }     return ;
}

上一篇:hdu 1564 Play a game(博弈找规律)


下一篇:Android SDK +Eclipse+ADT+CDT+NDK 开发环境在windows 7下的搭建