最近又在水网络流qwq

但是以后不卷了

老巴实的做些我能做的水题去了qwq

这道题不难想，

但是不太好实现(其实也不难实现,

首先,

我们直接跑一遍最大流,

如果 \(maxflow \geq c\) 的话,

我们就直接输出 \(possible\) 就是了.

很显然，

我们一定存在一个流与 \(c\) 相等，

因为我们的流量是可以取到 \(0 \sim maxflow\) 的所有值的.

比较麻烦的是下面,

在我们的 \(maxflow < s\) 的时候,

修改哪些边.

其实也不难,

我们想一下,

限制我们最大流的是哪些边,

或者说,

哪些边已经跑满了(流量 == 容量),

很显然,

就是最小割里的边,

我们只需要把最小割里的边拿出来,

按照题目中给的要求排序,

再分别修改它们的容量为 \(c\) ,

修改之后,

跑最大流,

注意一下,

我们不必每次都重新跑最大流,

我们只需要在我们跑完最大流后的图上跑就可以了,

因为原先存在的流量肯定都还存在,

我们只需要在当前的 \(maxflow\) 的基础上进行增广就可以了.

(所以记得把当前所有边的流量存一份)

这边建议使用 \(dinic\) 算法,

因为它不需要任何修改,

也不需要其他预处理,

像 \(ISAP\) 就需要重新预处理,

于是就有了如下代码.

\(code:\)

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
typedef long long ll;
const int maxn = 4e4 + 5, inf = 1 << 30;
int now[maxn], d[maxn], s = 1, t, n;
int tot, from[maxn], to[maxn], nxt[maxn], cap[maxn], head[maxn], faq[maxn];//faq用来存储跑完最大流后的所有边的流量,方便以后使用
ll maxflow;
queue <int> q;
struct node{//用来储存最小割中的边
	int from, to, id;
	bool operator < (const node& x) const {//根据题目中的要求重载运算符
		if (from == x.from) return to < x.to;
		return from < x.from;
	}
} edge[maxn];
int read(){
	int x = 0, f = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9'){
		if (ch == '-') f = -1;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9'){
		x = (x << 3) + (x << 1) + (ch ^ 48);
		ch = getchar();
	}
	return x * f;
}
void add(int u, int v, int w){
	from[++tot] = u, to[tot] = v, cap[tot] = w, nxt[tot] = head[u], head[u] = tot;
}
bool BFS(){
	memset(d, 0, sizeof(int) * (n + 1));
	while (q.size()) q.pop();
	q.push(s); d[s] = 1; now[s] = head[s];
	while (q.size()){
		int x = q.front(); q.pop();
		for (int i = head[x]; i; i = nxt[i]){
			int y = to[i];
			if (!d[y] && cap[i]){
				q.push(y);
				d[y] = d[x] + 1;
				now[y] = head[y];
				if (y == t) return true;
			}
		}
	}
	return false;
}
int dinic(int x, int flow){
	if (x == t || flow == 0) return flow;
	int rest = flow, k, i;
	for (i = now[x]; i && rest; i = nxt[i]){
		int y = to[i];
		if (d[y] == d[x] + 1 && cap[i]){
			k = dinic(y, min(rest, cap[i]));
			if (!k) d[y] = 0;
			cap[i] -= k;
			cap[i ^ 1] += k;
			rest -= k;
		}
	}
	now[x] = i;
	return flow - rest;
}
int judge(){//qwq为修改当前这条弧的容量后增加的流量
	ll flow = 0, qwq = 0;
	while (BFS())//这就是为什么我建议用dinic了,这里直接用就可以,完全没必要改任何一点,而ISAP需要重新初始化
		while (flow = dinic(s, inf)) qwq += flow;
	return qwq;//返回修改后增加的流量
}
int main(){
	n = read(); int e = read(), c = read(), qwq = 1;
	while (n){
		printf("Case %d: ", qwq++);
		tot = 1, maxflow = 0, t = n;
		for (int i = 1; i <= n; i++) head[i] = d[i] = 0;
		for (int i = 1; i <= e; i++){
			int u = read(), v = read(), w = read();
			add(u, v, w); add(v, u, 0);
		}
		ll flow = 0;
		while (BFS())//正常的dinic
			while (flow = dinic(s, inf)) maxflow += flow;
		c -= maxflow;//将c与maxflow作差,这样可以方便之后的操作(我认为)
		if (c <= 0) printf("possible");//maxflow>=c,输出possible
		else {//判断是否存在合法的弧,这里合法的弧指的是这条弧修改后能使得maxflow>=c
			int num = 0;
			for (int i = 2; i <= tot; i++) faq[i] = cap[i];//保存当前图上的所有边的流量
			for (int i = 2; i <= tot; i += 2){//寻找最小割中的边,这里我们只需要找连的边,不需要找我们建的反向边
				if (cap[i] == 0){//根据最大流最小割定理我们可知,最小割中的边的流量都与容量相等
					edge[++num].from = from[i];
					edge[num].to = to[i];
					edge[num].id = i;
				}
			}
			sort(edge + 1, edge + num + 1);//排序,因为我们需要按照题目中要求的顺序输出.
			bool ok = 1;//用来判断是否已经找到合法的弧
			for (int i = 1; i <= num; i++){
				cap[edge[i].id] = c;
				if (judge() >= c){//当前的弧合法
					if (ok){
						ok = 0;
						printf("possible option:(%d,%d)", edge[i].from, edge[i].to);
					}
					else printf(",(%d,%d)", edge[i].from, edge[i].to);
				}
				for (int j = 2; j <= tot; j++) cap[j] = faq[j];
			}
			if (ok) printf("not possible");//没有找到合法的弧
		}
		printf("\n");
		n = read(), e = read(), c = read();
	}
	return 0;
}

其实最开始的时候我犯了一个错误，

就是只找到一条增广路的时候就返回流量，

实际上我们应该跑完这遍 \(DFS\) ,

否则就会少增广.

完结撒花~