UVA11248 网络扩容（枚举割边扩充）

题意：
给你一个有向图，问你从1到n的最大流是多少？如果流量大于等于C那么直接输出一个串，否则输出只扩充一条边的流量就可以达到1->n大于等于C的所有边，如果扩充不了就

输出另一个串。

Sample Input
4 4 5
1 2 5
1 3 5
2 4 5
3 4 5
4 4 5
1 2 1
1 3 5
2 4 5
3 4 1
4 4 5
1 2 1
1 3 1
2 4 1
3 4 1
0 0 0

Output for Sample Input
Case 1: possible
Case 2: possible option:(1,2),(3,4)
Case 3: not possible

思路：
很容易想到的一点就是扩展后有作用的点肯定是割边，那么我们可以先跑一遍最大流把割边找出来，然后枚举割边，扩充割边流量，看最大流是否大于等于C，但是这样会TLE，有两个比较有用的优化，就是每次都在残余网络上改流量，然后加上残余网络之前跑出来的流量，还有一个优化就是跑最大流的时候，如果当前流量大于等于C了就已经满足了，没必要再跑了。

#include<queue>

#include<stdio.h>

#include<string.h>

#include<algorithm>

#define N_node 100 + 5

#define N_edge 20000 + 10

#define INF 2005000000

using namespace std;

typedef struct

{

int from ,to ,next;

long long cost;

}STAR;

typedef struct

{

int x ,t;

}DEP;

typedef struct

{

int a ,b;

}EDGE;

STAR E[N_edge] ,mkE[N_edge];

EDGE edge[N_edge] ,Ans_Edge[N_edge];

DEP xin ,tou;

int list[N_node] ,list2[N_node] ,mklist[N_node] ,tot;

int deep[N_node];

void add(int a ,int b ,long long c)

{

E[++tot].from = a;

E[tot].to = b;

E[tot].cost = c;

E[tot].next = list[a];

list[a] = tot;

E[++tot].from = b;

E[tot].to = a;

E[tot].cost = 0;

E[tot].next = list[b];

list[b] = tot;

}

bool camp(EDGE a ,EDGE b)

{

return a.a < b.a || a.a == b.a && a.b < b.b;

}

long long minn(long long a ,long long b)

{

return a < b ? a : b;

}

bool BFS_Deep(int s ,int t ,int n)

{

memset(deep ,255 ,sizeof(deep));

xin.x = s ,xin.t = 0;

deep[s] = 0;

queue<DEP>q;

q.push(xin);

while(!q.empty())

{

tou = q.front();

q.pop();

for(int k = list[tou.x] ;k ;k = E[k].next)

{

xin.x = E[k].to;

xin.t = tou.t + 1;

if(deep[xin.x] != -1 || !E[k].cost)

continue;

deep[xin.x] = xin.t;

q.push(xin);

}

}

for(int i = 0 ;i <= n ;i ++)

list2[i] = list[i];

return deep[t] != -1;

}

long long DFS_Flow(int s ,int t ,long long flow ,long long C)

{

if(s == t) return flow;

long long nowflow = 0;

for(int k = list2[s] ;k ;k = E[k].next)

{

list2[s] = k;

int to = E[k].to;

long long c = E[k].cost;

if(deep[to] != deep[s] + 1 || !c) continue;

long long tmp = DFS_Flow(to ,t ,minn(c ,flow - nowflow) ,C);

nowflow += tmp;

E[k].cost -= tmp;

E[k^1].cost += tmp;

if(nowflow == flow) break;

}

if(!nowflow) deep[s] = 0;

return nowflow;

}

long long DINIC(int s ,int t ,int n ,long long C)

{

long long Ans = 0;

while(BFS_Deep(s ,t ,n) && Ans < C)

{

Ans += DFS_Flow(s ,t ,INF ,C);

}

return Ans;

}

int main ()

{

int n ,m ,C ,cas = 1;

int a ,b ,c ,i ,j;

while(~scanf("%d %d %d" ,&n ,&m ,&C) && n + m + C)

{

memset(list ,0 ,sizeof(list)) ,tot = 1;

for(i = 1 ;i <= m ;i ++)

{

scanf("%d %d %d" ,&a ,&b ,&c);

add(a ,b ,(long long)c);

}

long long Ans = DINIC(1 ,n ,n ,C);

printf("Case %d: " ,cas ++);

if(Ans >= C)

{

printf("possible\n");

continue;

}

int nowid = 0;

for(i = 2 ;i <= tot ;i += 2)

{

mkE[i] = E[i] ,mkE[i+1] = E[i+1];

if(!E[i].cost)

{

edge[++nowid].a = E[i].from;

edge[nowid].b = E[i].to;

}

}

for(i = 1 ;i <= n ;i ++)

mklist[i] = list[i];

int Ans_Id = 0;

int mktot = tot;

for(i = 1 ;i <= nowid ;i ++)

{

add(edge[i].a ,edge[i].b ,C);

long long tmp = DINIC(1 ,n ,n ,C);

if(tmp + Ans >= C) Ans_Edge[++Ans_Id] = edge[i];

tot = mktot;

for(j = 2 ;j <= tot ;j ++) E[j] = mkE[j];

for(j = 1 ;j <= n ;j ++) list[j] = mklist[j];

}

if(!Ans_Id)

{

puts("not possible");

continue;

}

sort(Ans_Edge + 1 ,Ans_Edge + Ans_Id + 1 ,camp);

printf("possible option:");

for(i = 1 ;i <= Ans_Id ;i ++)

if(i != 1) printf(",(%d,%d)" ,Ans_Edge[i].a ,Ans_Edge[i].b);

else printf("(%d,%d)" ,Ans_Edge[i].a ,Ans_Edge[i].b);

puts("");

}

return 0;

}

巴特西

UVA11248 网络扩容（枚举割边扩充）

最新文章

热门文章