題意：
? ? ? 給你一個有向圖，問你從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，有兩個比較有用的優(yōu)化，就是每次都在殘余網(wǎng)絡(luò)上改流量，然后加上殘余網(wǎng)絡(luò)之前跑出來的流量，還有一個優(yōu)化就是跑最大流的時候，如果當(dāng)前流量大于等于C了就已經(jīng)滿足了，沒必要再跑了。




#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;
}


























《新程序員》：云原生和全面數(shù)字化實踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的UVA11248 网络扩容（枚举割边扩充）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。