POJ 1087 A Plug for UNIX (網絡最大流)
POJ 1087 A Plug for UNIX
鏈接:http://poj.org/problem?id=1087
題意:有n(1≤n≤100)個插座,每個插座用一個數字字母式字符串描述(至多有24 個字符)。有m(1≤m≤100)個設備,每個設備有名稱,以及它使用的插頭的名稱;插頭的名稱跟它所使用的插座的名稱是一樣的;設備名稱是一個至多包含24 個字母數字式字符的字符串;任何兩個設備的名稱都不同;有k(1≤k≤100)個轉換器,每個轉換器能將插座轉換成插頭。
樣例:
4
A
B
C
D
5
laptop B
phone C
pager B
clock B
comb X
3
B X
X A
X D
思路:建立一個匯點,每個插座和匯點連邊,流量代表該種插座的個數。建立一個源點,源點和每個設備連邊,流量為1。每個轉換器將兩個插座連邊,流量為INF。然後求最大流。答案就是設備的個數減去最大流。
細節:這道題在建圖的時候比較惡心。需要注意的是,在m個設備和插座以及k個轉換器的數據中,可能有之前沒有出現過的設備。所以必須將插座的信息存起來,可以用map來存插座對應的點。
代碼:
/*
ID: [email protected]
PROG:
LANG: C++
*/
#include