程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> POJ1087A Plug for UNIX(會議室的插座)——最大流

POJ1087A Plug for UNIX(會議室的插座)——最大流

編輯：C++入門知識

POJ1087A Plug for UNIX(會議室的插座)——最大流

題目描述：
現在由你負責布置Internet 聯合組織首席執行官就職新聞發布會的會議室。
由於會議室修建時被設計成容納全世界各地的新聞記者，因此會議室提供了多種電源插座用
以滿足（會議室修建時期）各國不同插頭的類型和電壓。不幸的是，會議室是很多年前修建的，
那時新聞記者很少使用電子設備，所以會議室對每種插座只提供了一個。新聞發布會時，新聞記
者需要使用許多電子設備，如手提電腦，麥克風，錄音機，傳呼機等等。盡管這些設備很多可以
使用電池，但是由於發布會時間很長並且是單調乏味的，記者們希望能夠使用盡可能多的設備（這
些設備需要使用插座），以打發時間。
在發布會之前，你收集了記者們使用的設備的信息，開始布置會議室。你注意到有些設備的
插頭沒有合適的插座可用。你懷疑這些設備來自那些在修建會議室時不存在的國家。對有些插座
來說，有多個設備的插頭可以使用。而對另一些插座來說，沒有哪些設備的插頭可以用得上。
為了試圖解決這個問題，你光顧了附近的商店，商店出售轉換器，這些轉換器可以將一種插
頭轉換成另一種插頭。而且轉換器可以串聯。商店沒有足夠多的轉換器類型，滿足所有的插頭和
插座的組合，但對於已有某種轉換器，總是可以提供無限多個。

輸入描述：
輸入文件包含多個測試數據。輸入文件的第一行為一個整數N，然後隔一個空行之後是N 個
輸入塊，每個輸入塊對應一個測試數據。輸入塊之間用空行隔開。每個輸入塊格式為：
每個輸入塊的第一行為一個正整數n，1≤n≤100，表示會議室提供的插座個數；接下來n
行列出了會議室提供的n 個插座，每個插座用一個數字字母式字符串描述（至多有24 個字符）；
接下來一行為一個正整數m，1≤m≤100，表示待插入的設備個數；接下來m 行中，每行首
先是設備的名稱，然後是它使用的插頭的名稱；插頭的名稱跟它所使用的插座的名稱是一樣的；
設備名稱是一個至多包含24 個字母數字式字符的字符串；任何兩個設備的名稱都不同；設備名稱
和插頭之間用空格隔開；
接下來一行為一個正整數k，1≤k≤100，表明可以使用的轉換器種數；接下來的k 行，每行
描述了一種轉換器：首先是轉換器提供的插座類型，中間是一個空格，然後是插頭的類型。

輸出描述：
對輸入文件中的每個測試數據，輸出一個非負整數，表明至少有多少個設備無法插入。

頂多有200個插座，100個設備。源點到各個設備建一條cap為1的邊，各個插座到匯點建一條cap為1的邊，各個設備到匹配的插座建一條cap為1的邊，插座之間的轉換建一條cap為INF的邊，求最大流

ISAP Memory: 336K Time: 32MS

#include
#include
#include
#include
#include
#include
const int maxn=400;
const int INF=0x3f3f3f3f;
using namespace std;
int n,s,t;
struct Edge{
    int from,to,cap,flow;
    Edge(int u,int v,int c,int f):from(u),to(v),cap(c),flow(f){}
};
vector edges;
vector G[maxn];
int gap[maxn],d[maxn],cur[maxn],p[maxn];
inline void addedge(int u,int v,int c){
    edges.push_back(Edge(u,v,c,0));
    edges.push_back(Edge(v,u,0,0));
    int m=edges.size();
    G[u].push_back(m-2);
    G[v].push_back(m-1);
}
int ISAP(){
    memset(cur,0,sizeof(cur));
    memset(d,0,sizeof(d));
    memset(gap,0,sizeof(gap));
    int x=s,flow=0,a=INF;
    while(d[s]e.flow&&d[e.to]+1==d[x]){
                p[e.to]=G[x][i];
                cur[x]=i;
                x=e.to;
                ok=1;
                a=min(a,e.cap-e.flow);
                break;
            }
        }
        if(!ok){
            int m=n;
            for(int i=0;ie.flow) m=min(m,d[e.to]);
            }
            if(--gap[d[x]]==0) break;
            gap[d[x]=m+1]++;
            cur[x]=0;
            if(x!=s) x=edges[p[x]].from;
        }
    }
    return flow;
}
map rec;
map dev;
int N,M,K,cnt,cmt;
void Init(){
    cnt=0,cmt=200;
    s=302,t=303;
    cin>>N;
    for(int i=0;i>s;
        if(!rec.count(s)) rec[s]=++cnt;
        addedge(rec[s],t,1);
    }
    cin>>M;
    for(int i=0;i>s1>>s2;
        dev[s1]=++cmt;
        if(!rec.count(s2)) rec[s2]=++cnt;
        addedge(dev[s1],rec[s2],1);
        addedge(s,dev[s1],1);
    }
    cin>>K;
    for(int i=0;i>s1>>s2;
        if(!rec.count(s1)) rec[s1]=++cnt;
        if(!rec.count(s2)) rec[s2]=++cnt;
        addedge(rec[s1],rec[s2],INF);
    }
    n=cnt+cmt-200+2;
}
int main()
{
    Init();
    printf(%d
,M-ISAP());
    return 0;
}