http://poj.org/problem?id=1087

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=82835#problem/C

n A socket ,m An electrical appliance and its corresponding socket ,k Two converters , The former can be converted into the latter , Ask at least how many devices do not have sockets , There is no limit to the number of Converters
Maximum flow , From the source to the socket , Capacity of 1, The electrical appliances build the edge to the meeting point , Capacity of 1, The corresponding socket is connected with the electric appliance , Capacity of 1, The former socket is transformed into the latter one ,
The back socket is bordered on the front socket , The capacity is infinite , The maximum current obtained is the most paired electrical apparatus .

Part of the network flow is going to be , But how to build a map still needs to learn

Code ：

```#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
#define N 1005
#define INF 0xfffffff
int G[N][N], Layer[N];
char s[N][];
bool CanLine(char s1[], char s2[]) /// Judge whether the adapter is the same
{
if(strcmp(s1, s2)==)
return true;
return false;
}
bool BFS(int Start, int End)
{
queue<int>Q;
Q.push(Start);
memset(Layer, -, sizeof(Layer));
Layer[Start] = ;
while(Q.size())
{
int u = Q.front();
Q.pop();
if(u==End) return true;
for(int i=; i<=End; i++)
{
if(Layer[i]==- && G[u][i])
{
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(G[u][i], MaxFlow-uflow);
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))
MaxFlow += DFS(Start, INF, 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++) /// The plug comes from 1~n
scanf("%s", s[i]);
scanf("%d", &m);
for(i=; i<=m; i++) /// Mobile phone from n~n+m, Ignore the name of the phone
scanf("%*s%s", s[i+n]);
scanf("%d", &k);
///Ki It's the starting point for the transition head to enter , Kj It's the starting point of the head change , Start It's the source ,Ｅｎｄ It's the meeting point
int Ki = n+m, Kj = Ki+k, Start = Kj+k+, End = Start+;
for(i=; i<=k; i++) /// The entry of the converter n+m~n+m+k, The output of the converter comes from n+m+k~n+m+2*k
{
/// Connect the in and out
scanf("%s%s", s[Ki+i], s[Kj+i]);
G[Ki+i][Kj+i] = INF; /// The converter offers unlimited
}
for(i=; i<=m; i++) /// Build mobile phones and Converters , The relationship between sockets
{
for(j=; j<=n; j++) /// Match whether the mobile phone and socket can be connected directly
if(CanLine(s[i+n], s[j]))
G[i+n][j]=true;
for(j=; j<=k; j++) /// Match whether the mobile phone and the converter can be connected
if(CanLine(s[i+n], s[Ki+j]))
G[i+n][Ki+j]=true;
}
for(i=; i<=k; i++) /// Build converters and Converters , The relationship between sockets
{
for(j=; j<=k; j++) /// Match converter and converter into , The converter offers unlimited , Direct maximum
if(i!=j && CanLine(s[Kj+i], s[Ki+j]))
G[Kj+i][Ki+j] = INF;
for(j=; j<=n; j++) /// Match the relationship between converter outlet and socket
if(CanLine(s[Kj+i], s[j])==true)
G[Kj+i][j] = true;
}
for(i=; i<=m; i++) /// The relationship between source and mobile phone
G[Start][n+i] = true;
for(i=; i<=n; i++) /// The relationship between socket and sink
G[i][End] = true;
printf("%d\n", m-Dinic(Start, End));
}
return ;
}```

## （ Network flow Templates ）A Plug for UNIX -- poj -- 1087 More articles about

1. C - A Plug for UNIX POJ - 1087 Network flow

You are in charge of setting up the press room for the inaugural meeting of the United Nations Inter ...

2. A Plug for UNIX POJ - 1087( The template questions There's nothing to say .. Just one map)

The question : Several kinds of plugs , There's only one of each , But there's an infinite number of plug Converters , converter (a,b) signify You can put b Convert to a, There are several devices , Each device corresponds to a plug , Find the number of devices that cannot match the plug This problem can be solved by bipartite graph , I use the most ...

3. C - A Plug for UNIX - poj 1087（ Maximum flow ）

The main idea of the topic : The meaning of this question is a little painful , It took a long time to see what it meant , Yes N A socket , These sockets are of a certain type, which can only charge this type of electrical appliances , Next, I'll give you M It's an electrical appliance , And the plug type of the appliance , also K It's a kind of converter , You can convert one type to another , transformation ...

4. （ Network flow Templates Edmonds-Karp）Drainage Ditches --POJ --1273

link : http://poj.org/problem?id=1273 Drainage Ditches Time Limit: 1000MS   Memory Limit: 10000K Total ...

5. POJ 1087 A Plug for UNIX / HDU 1526 A Plug for UNIX / ZOJ 1157 A Plug for UNIX / UVA 753 A Plug for UNIX / UVAlive 5418 A Plug for UNIX / SCU 1671 A Plug for UNIX （ Network flow ）

POJ 1087 A Plug for UNIX / HDU 1526 A Plug for UNIX / ZOJ 1157 A Plug for UNIX / UVA 753 A Plug for ...

6. poj 1087 C - A Plug for UNIX Network flow, maximum flow

C - A Plug for UNIXTime Limit: 20 Sec Memory Limit: 256 MB Topic linking http://acm.hust.edu.cn/vjudge/contes ...

7. poj 1087 A Plug for UNIX（ String number for drawing ）

A Plug for UNIX Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 14862   Accepted: 5026 ...

8. Power Network POJ - 1459 [ Network flow template ]

http://poj.org/problem?id=1459 Um. , Network flow template ... A graph with multiple sources and sinks , Super meeting point and power plant , Users connect to super sink Status Accepted Time 391ms Memor ...

9. uva753 A Plug for UNIX Network flow, maximum flow

C - A Plug for UNIX    You are in charge of setting up the press room for the inaugural meeting of t ...

## Random recommendation

1. SQL Little note -- Some convenient reference SQL sentence -- Check as you use

SQL sentence sentence grammar AND / OR SELECT column_name(s)FROM table_nameWHERE conditionAND|OR condition ALTER TABL ...

2. MySQL Enterprises often use cluster diagram

mysql Cluster architecture picture 1.mysql Common cluster architecture of enterprises In small and medium-sized Internet enterprises .mysql In general, the cluster is the architecture shown in the figure above .WEB When the node reads the database, it reads dbproxy The server .dbproxy The server through to S ...

3. 140. Word Break II

subject : Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where e ...

4. mysql- Create a function , Stored procedures and views

1. Create a function  mysql>delimiter //  mysql>create function Function name ( Parameters 1 Parameters 1 type ,...) returns Return type       >be ...

5. Mysql Security mechanism

stay mysql Next mysql In the library 6 A permission table mysql.user User field , Permission fields , Secure fields , Resource control fields mysql.db . mysql.host User field , Permission fields mysql.tables_p ...

6. Big data HBase

Big data HBase Data insertion optimization multithread parallel insertion test case One . introduction : The last article mentioned about HBase Insert five parameters into the performance optimization design , From the perspective of parameter configuration, we provide a performance test environment experimental code . According to the feedback from netizens , be based on ...

7. Chapter 2 Open Book——18

"Wow," Mike said. "It's snowing."I looked at the little cotton fluffs that were ...

8. Android Development Pull up to load more functions