题意：
给定一个有向网络，每条边均有一个容量。问是否存在一个从点1到点N，流量为C的流。如果不存在，是否可以恰好修改一条弧的容量，使得存在这样的流？
分析：
先跑一遍最大流，如果最大流大于等于C，则输possible。如果最大流小于C，则表明需要修改边的流量。很显然，需要修改的弧一定是满流的弧。但是如果直接暴力会超时，所以我们可以有两个优化。
1.第一次求完最大流以后，把每条弧的流量保存下来，每次修改完一条弧的容量以后，都从当前残量网络开始继续增广。
2.每次不需要增广到最大流，当流量大于等于C的时候就停止增广（不过不加这个优化好像也没事，反正我没加··）
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector> using namespace std;
const int maxn=+;
const int maxm=+;
const int INF=;
struct Dinic{
int head[maxn],Next[maxm],to[maxm],from[maxm],cap[maxm],flow[maxm];
int n,m,s,t,sz;
bool vis[maxn];
int d[maxn],cur[maxn];
void init(int n){
this->n=n;
sz=-;
memset(head,-,sizeof(head));
}
void add_edge(int a,int b,int c){
++sz;
to[sz]=b;Next[sz]=head[a];head[a]=sz;
cap[sz]=c;flow[sz]=,from[sz]=a;;
++sz;
to[sz]=a;Next[sz]=head[b];head[b]=sz;
cap[sz]=c;flow[sz]=c,from[sz]=b;
}
bool BFS(){
memset(vis,,sizeof(vis));
for(int i=;i<=n;i++)d[i]=INF;
queue<int>Q;
d[s]=,vis[s]=;
Q.push(s);
while(!Q.empty()){
int u=Q.front();Q.pop();
for(int i=head[u];i!=-;i=Next[i]){
int v=to[i];
if(cap[i]>flow[i]&&!vis[v]){
vis[v]=;
d[v]=d[u]+;
Q.push(v);
}
}
}
return vis[t];
}
int DFS(int x,int a){
if(x==t||a==)return a;
int Flow=,f;
for(int& i=cur[x];i!=-;i=Next[i]){
int v=to[i];
if(d[v]==d[x]+&&(f=DFS(v,min(a,cap[i]-flow[i])))>){
Flow+=f;
flow[i]+=f;
flow[i^]-=f;
a-=f;
if(a==)break;
}
}
return Flow;
}
int Maxflow(int s,int t){
this->s=s;this->t=t;
int Flow=;
while(BFS()){
for(int i=;i<=n;i++)cur[i]=head[i];
Flow+=DFS(s,INF);
}
return Flow;
}
}dinic;
struct Edge{
int from,to;
bool operator <(const Edge& rhs)const{
return from<rhs.from||(from==rhs.from&&to<rhs.to);
}
};
vector<Edge>ans;
int kase,N,E,C;
int main(){
kase=;
while(scanf("%d%d%d",&N,&E,&C)!=EOF&&(N||E||C)){
++kase;
printf("Case %d: ",kase);
ans.clear();
dinic.init(N);
int u,v,c;
for(int i=;i<=E;i++){
scanf("%d%d%d",&u,&v,&c);
dinic.add_edge(u,v,c);
}
int Maxflow=dinic.Maxflow(,N);
if(Maxflow>=C){
printf("possible\n");
}else{
int FLOW[maxm];
for(int i=;i<=dinic.sz;i++){
FLOW[i]=dinic.flow[i];
}
int CAP,c=C-Maxflow;
for(int i=;i<=dinic.sz;i+=){
if(dinic.cap[i]==dinic.flow[i]){ for(int i=;i<=dinic.sz;i++)dinic.flow[i]=FLOW[i];
CAP=dinic.cap[i];
dinic.cap[i]=C;
dinic.cap[i^]=C;
Maxflow=dinic.Maxflow(,N);
if(Maxflow>=c){
ans.push_back((Edge){dinic.from[i],dinic.to[i]});
}
dinic.cap[i]=CAP;
dinic.cap[i^]=CAP;
for(int i=;i<=dinic.sz;i++)dinic.flow[i]=FLOW[i];
}
}
if(ans.size()==){
printf("not possible\n");
}else{
sort(ans.begin(),ans.end());
printf("possible option:");
for(int i=;i<ans.size();i++){
if(i!=)printf(",");
printf("(%d,%d)",ans[i].from,ans[i].to);
}
printf("\n");
}
}
}
return ;
}