题目链接：https://vjudge.net/contest/144904#problem/A
题意：给定一个有向网络，每条边均有一个容量。问是否存在一个从点1到点N，流量为C的流。如果不存在，是否可以恰好修改一条弧的容量，使得存在这样的流？
分析：
首先找到最大流，如果发现大于等于C，就得到解，如果小于C的话，枚举最小割。这时，之前的最大流保存下来，清空流量，改变最小割的容量，再求最大流。
include <bits/stdc++.h>
using namespace std; const int maxn = + ;
const int INF = 0x3f3f3f3f; struct Edge {
int from,to,cap,flow;
}; bool operator < (const Edge& a,const Edge& b) {
return a.from < b.from || (a.from==b.from&&a.to<b.to);
} struct Dinic {
int n,m,s,t;
vector<Edge> edges;
vector<int> G[maxn];
bool vis[maxn];
int d[maxn];
int cur[maxn]; void init(int n) {
for(int i=;i<n;i++)
G[i].clear();
edges.clear();
} void ClearFlow() {
for(int i=;i<edges.size();i++) {
edges[i].flow = ;
}
} void AddEdge(int from,int to,int cap) {
edges.push_back((Edge){from,to,cap,});
edges.push_back((Edge){to,from,,});
m = edges.size();
G[from].push_back(m-);
G[to].push_back(m-);
} bool BFS() {
memset(vis,,sizeof(vis));
queue<int> Q;
Q.push(s);
vis[s] = ;
d[s] = ;
while(!Q.empty()) {
int x = Q.front();
Q.pop();
for(int i=;i<G[x].size();i++) {
Edge& e = edges[G[x][i]];
if(!vis[e.to]&&e.cap>e.flow) {
vis[e.to] = ;
d[e.to] = d[x] + ;
Q.push(e.to);
}
}
}
return vis[t];
} int DFS(int x,int a) {
if(x==t||a==) return a;
int flow =,f;
for(int& i=cur[x];i<G[x].size();i++) {
Edge& e = edges[G[x][i]];
if(d[x]+==d[e.to]&&(f=DFS(e.to,min(a,e.cap-e.flow)))>) {
e.flow +=f;
edges[G[x][i]^].flow -=f;
flow +=f;
a-=f;
if(a==) break;
}
}
return flow;
} int Maxflow(int s,int t) {
this->s = s;
this->t = t;
int flow = ;
while(BFS()) {
memset(cur,,sizeof(cur));
flow +=DFS(s,INF);
}
return flow;
} vector<int> Mincut() {
vector<int> ans;
for(int i=;i<edges.size();i++) {
Edge& e = edges[i];
if(vis[e.from]&&!vis[e.to]&&e.cap>)
ans.push_back(i);
}
return ans;
} void Reduce () {
for(int i=;i<edges.size();i++)
edges[i].cap -=edges[i].flow;
} }; Dinic g; int main()
{
int kase = ;
int n,e,c;
while(scanf("%d%d%d",&n,&e,&c)==&&n) {
g.init(n);
for(int i=;i<e;i++) {
int u,v,cap;
scanf("%d%d%d",&u,&v,&cap);
u--;v--;
g.AddEdge(u,v,cap);
}
printf("Case %d: ",kase ++);
int flow = g.Maxflow(,n-);
if(flow>=c) printf("possible\n"); else {
vector<int> cut = g.Mincut();
g.Reduce();
vector<Edge> ans;
for(int i=;i<cut.size();i++) {
Edge& e = g.edges[cut[i]];
int temp = e.cap; ///
e.cap = c;
g.ClearFlow();
if(flow+g.Maxflow(,n-)>=c)
ans.push_back(e);
e.cap = temp; ///
}
if(ans.empty())
printf("not possible\n");
else {
sort(ans.begin(),ans.end());
printf("possible option:(%d,%d)",ans[].from+,ans[].to + );
for(int i=;i<ans.size();i++) {
printf(",(%d,%d)",ans[i].from+,ans[i].to+);
}
puts("");
}
}
} return ;
}