本文主要是介绍poj_1087_最大流，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目描述：
给出插座类型。给出设备个数和对应的插座类型。给出插座转接类型。求最后最少有几个设备无法接上插座。
解题思路：
最大流，多源多终点，转为单源单终点的图做。求出来的最大流为最多能接上的设备数。
注意这里的数组大小，，要开到最少402。。。。。
代码：
#include <stdio.h>
#include <stdlib.h>
#define MAX 500
int c[MAX][MAX], pre[MAX], max_flow, que[10000];
char receptacle[MAX][25];
void ford_fulkerson(int src, int des){
int x, y, tmp, min;
max_flow = 0;
while(edmonds_karp(src,des)!=0){
//printf("max_flow:%d\n",max_flow);
min = MAX;
x = pre[des];
y = des;
while(y!=src){
if(c[x][y]<min)
min = c[x][y];
tmp = x;
x = pre[x];
y = tmp;
}
max_flow += min;
//update
x = pre[des];
y = des;
while(y!=src){
c[x][y] -= min;
c[y][x] += min;
tmp = x;
x = pre[x];
y = tmp;
}
}
}
int edmonds_karp(int src, int des){
int front, rear, v, i, visit[MAX];
memset(visit, 0, sizeof(visit));
front = rear = 0;
que[rear++] = src;
visit[src] = 1;
while(front != rear){
v = que[front++];
for(i=1;i<=des;i++){
if(!visit[i] && c[v][i]){
que[rear++] = i;
pre[i] = v;
visit[i] = 1;
if(i == des)
return 1;
}
}
}
return 0;
}
main()
{
char tmp1[25],tmp2[25];
int tmp, i, j, n, m, k, x, y;
memset(c,0,sizeof(c));
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%s",receptacle[i]);
}
tmp = n;
scanf("%d",&m);
for(i=1;i<=m;i++){
scanf("%s %s",tmp1, tmp2);
for(j=1;j<=n;j++)
if(strcmp(receptacle[j],tmp2)==0)
break;
if(j>n){
n++;
strcpy(receptacle[n],tmp2);
}
c[0][j]++; // 0 as src
}
scanf("%d",&k);
for(i=1;i<=k;i++){
scanf("%s %s",tmp1,tmp2);
for(j=1;j<=n;j++)
if(strcmp(tmp1,receptacle[j])==0)
break;
if(j>n){
n++;
strcpy(receptacle[n],tmp1);
}
x = j;
for(j=1;j<=n;j++)
if(strcmp(tmp2,receptacle[j])==0)
break;
if(j>n){
n++;
strcpy(receptacle[n],tmp2);
}
y=j;
c[x][y] = MAX;
}
for(i=1;i<=tmp;i++)
c[i][n+1] = 1;