题意就不再说了,主要是想说一下为啥要拆点
POJ 2112跟本题很相似,也是二分,但它就没用拆点,本题就用了
为啥呢? 因为POJ2112上建的图中是一个很明显的二分图,也就是左边的点绝对不会跟左边的点去连边的。而本题中就不一样了,任何点之间都可能有边。
会出现这种情况,1->2->3,这是一条链,而1->2最短路为1,2->3为1,1->3为 2,此时如果我们限制最大距离为1的话,建的新图中必然有1->2,2-3, 然后我们就发现问题了,新图中1和3也会间接的连接起来,而我们显然是不想这么让它流的。这就需要拆点了,对每个点x,拆成x'和x'',然后x'和x''之间有一条无限容量的边,这样的话,随便多少牛路过这个点都是可以的,如果i->j这条边符合了距离限制,就加i'->j'' 所有的边加完后,建立源点,对所有的x'连边,容量为已经有的牛,汇点的话,就用所有的j''连接汇点,容量就是能容纳的牛的数量。
这样一拆点,就发现之前的问题不复存在了,还是比如1->2->3这个例子,加的边是1’->2'',2'->3'' 不会有流从1流到3去,因为加的每条边都流向了汇点
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#define MAXN 555
#define MAXM 222222
#define INF 1000000007
using namespace std;
struct node
{
int ver; // vertex
int cap; // capacity
int flow; // current flow in this arc
int next, rev;
}edge[MAXM];
int dist[MAXN], numbs[MAXN], src, des, n;
int head[MAXN], e;
void add(int x, int y, int c)
{ //e记录边的总数
edge[e].ver = y;
edge[e].cap = c;
edge[e].flow = 0;
edge[e].rev = e + 1; //反向边在edge中的下标位置
edge[e].next = head[x]; //记录以x为起点的上一条边在edge中的下标位置
head[x] = e++; //以x为起点的边的位置
//反向边
edge[e].ver = x;
edge[e].cap = 0; //反向边的初始网络流为0
edge[e].flow = 0;
edge[e].rev = e - 1;
edge[e].next = head[y];
head[y] = e++;
}
void rev_BFS()
{
int Q[MAXN], qhead = 0, qtail = 0;
for(int i = 1; i <= n; ++i)
{
dist[i] = MAXN;
numbs[i] = 0;
}
Q[qtail++] = des;
dist[des] = 0;
numbs[0] = 1;
while(qhead != qtail)
{
int v = Q[qhead++];
for(int i = head[v]; i != -1; i = edge[i].next)
{
if(edge[edge[i].rev].cap == 0 || dist[edge[i].ver] < MAXN)continue;
dist[edge[i].ver] = dist[v] + 1;
++numbs[dist[edge[i].ver]];
Q[qtail++] = edge[i].ver;
}
}
}
void init()
{
e = 0;
memset(head, -1, sizeof(head));
}
int maxflow()
{
int u, totalflow = 0;
int Curhead[MAXN], revpath[MAXN];
for(int i = 1; i <= n; ++i)Curhead[i] = head[i];
u = src;
while(dist[src] < n)
{
if(u == des) // find an augmenting path
{
int augflow = INF;
for(int i = src; i != des; i = edge[Curhead[i]].ver)
augflow = min(augflow, edge[Curhead[i]].cap);
for(int i = src; i != des; i = edge[Curhead[i]].ver)
{
edge[Curhead[i]].cap -= augflow;
edge[edge[Curhead[i]].rev].cap += augflow;
edge[Curhead[i]].flow += augflow;
edge[edge[Curhead[i]].rev].flow -= augflow;
}
totalflow += augflow;
u = src;
}
int i;
for(i = Curhead[u]; i != -1; i = edge[i].next)
if(edge[i].cap > 0 && dist[u] == dist[edge[i].ver] + 1)break;
if(i != -1) // find an admissible arc, then Advance
{
Curhead[u] = i;
revpath[edge[i].ver] = edge[i].rev;
u = edge[i].ver;
}
else // no admissible arc, then relabel this vertex
{
if(0 == (--numbs[dist[u]]))break; // GAP cut, Important!
Curhead[u] = head[u];
int mindist = n;
for(int j = head[u]; j != -1; j = edge[j].next)
if(edge[j].cap > 0)mindist = min(mindist, dist[edge[j].ver]);
dist[u] = mindist + 1;
++numbs[dist[u]];
if(u != src)
u = edge[revpath[u]].ver; // Backtrack
}
}
return totalflow;
}
int F, P;
int now[MAXN], can[MAXN];
long long d[MAXN][MAXN];
void floyd(int n)
{
for(int k = 1; k <= n; k++)
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
if(d[i][k] + d[k][j] < d[i][j])
d[i][j] = d[i][k] + d[k][j];
}
int main()
{
int total = 0;
scanf("%d%d", &F, &P);
for(int i = 1; i <= F; i++)
{
scanf("%d%d", &now[i], &can[i]);
total += now[i];
}
for(int i = 1; i <= F; i++)
for(int j = 1; j <= F; j++)
if(i != j) d[i][j] = 2000000000000LL;
else d[i][j] = 0;
int u, v, w;
for(int i = 1; i <= P; i++)
{
scanf("%d%d%d", &u, &v, &w);
if(d[u][v] > w) d[u][v] = d[v][u] = w;
}
floyd(F);
long long low = 0, high = 0;
for(int i = 1; i <= F; i++)
for(int j = 1; j <= F; j++)
if(d[i][j] != 2000000000000LL) high = max(high, d[i][j]);
n = 2 * F + 2;
src = 1;
des = n;
long long ans = -1;
while(low <= high)
{
long long mid = (low + high) / 2;
init();
for(int i = 1; i <= F; i++)
for(int j = 1; j <= F; j++)
if(d[i][j] <= mid)
add(i + 1, j + 1 + F, INF);
for(int i = 1; i <= F; i++)
{
add(src, i + 1, now[i]);
add(i + 1 + F, des, can[i]);
}
rev_BFS();
int flow = maxflow();
//printf("dsfsd %d\n", flow);
if(flow == total)
{
ans = mid;
high = mid - 1;
}
else low = mid + 1;
}
printf("%lld\n", ans);
return 0;
}
分享到:
相关推荐
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj2516代码最小费用最大流
NULL 博文链接:https://128kj.iteye.com/blog/1750462
poj分类poj分类poj分类poj分类
西北工业大学POJ试题C++答案代码+课程设计
poj 百练 题目分类 poj 百练 题目分类
POJ题目分类POJ题目分类POJ题目分类
北大POJ1207-The 3n + 1 problem 解题报告+AC代码
该文档对poj大部分题目进行了分类,有利于喜欢在poj刷题的朋友
2505 2521 2538 2546 2551 2590 2593 2601 2665 2680 2739 2752 2761 2762 2777 2800 2891 2893 2992 3030 3041 3132 3159 3187 3204 3270 3277 3281 3297 3321 3414 3436 3461 3650 3663 3664 3672 3740
北大POJ3009-Curling 2.0【DFS+Vector+回溯+剪枝】 解题报告+AC代码
poj题目分类
北大POJ2195-Going Home【费用流】 解题报告+AC代码 http://blog.csdn.net/lyy289065406/article/details/6732762
POJ2186-Popular Cows ...【Tarjan+极大强连通分量+缩点】 解题报告+AC代码 http://hi.csdn.net/!s/BGDH68 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
【二分图顶点覆盖->最小割->最大流->Dinic算法求解】 解题报告+AC代码 http://hi.csdn.net/!s/WKVPR0 ----> 我的所有POJ解题报告 http://blog.csdn.net/lyy289065406/article/details/6642573
强大的poj分类 学做POJ必备 非最新,供参考
POJ 最接近点对问题 ACM北大 using namespace std; struct Point { float x; float y; };
北大POJ2002-Squares 解题报告+AC代码
pojACM题目分类,便于各类型同学分别做题有所参考
北大POJ初级-简单搜索 解题报告+AC代码