|
struct Dinic{
int n,m,s,t;
vector edges;
vector G[MAXN];// 邻接表，G[i][j]表示结点i的第j条边在e数组中的序号
bool vis[MAXN];
int d[MAXN];
int cur[MAXN];
void init(int n){
this->n=n;
for(int i=0;i<=n;i++)G[i].clear();
edges.clear();
}
void AddEdge(int from,int to,int cap){
Edge e;
e.from=from;e.to=to;e.cap=cap;e.flow=0;
edges.push_back(e);
e.from=from;e.to=to;e.cap=0;e.flow=0;
edges.push_back(e); m=edges.size();
G[from].push_back(m-2);
G[to].push_back(m-1);
}
bool BFS(){
CL(vis,0);
queue Q;
Q.push(s);
d[s]=0;
vis[s]=1;
while(!Q.empty()){
int x=Q.front();
Q.pop();
for(int i=0;ie.flow){
vis[e.to]=1;
d[e.to]=d[x]+1;
Q.push(e.to);
}
}
}
return vis[t];
}
int DFS(int x,int a){
if(x==t||a==0)return a;
int flow=0,f;
for(int& i=cur[x];i0){
e.flow+=f;
edges[G[x][i]^1].flow-=f;
flow+=f;
a-=f;
if(a==0)break;
}
}
return flow;
}
int Maxflow(int s,int t,int need){//)///求最大流 如果大于need就直接退出
this->s=s;this->t=t;
int flow=0;
while(BFS()){
CL(cur,0);
flow+=DFS(s,INF);
if(flow>need)return flow;
}
return flow;
}
// 注意返回类型
vector Mincut(){///求最小割集 在求最大流之后才能用，直接用
BFS();
vector ans;
for(int i=0;i0)ans.push_back(i);
}
return ans;
}
void Reduce(){//求剩余容量
for(int i = 0; i < edges.size(); i++) edges[i].cap -= edges[i].flow;
}
void ClearFlow(){//把当前流量flow清0
for(int i = 0; i < edges.size(); i++) edges[i].flow = 0;
}
};
bool cmp(const Edge& a,const Edge& b){
return a.from < b.from || (a.from == b.from && a.to < b.to);
}
Dinic solver;///一定要用g++提交 c++编译错误 一定不要忘记调用 init(des)
int main(){
int N,E,C,cas=0;
while(~scanf("%d%d%d",&N,&E,&C))
{
if(!N)break;
solver.init(N);
int a,b,c;
while(E--)
{
scanf("%d%d%d",&a,&b,&c);
solver.AddEdge(a,b,c);
}
int flow=solver.Maxflow(1,N,INF);
printf("Case %d: ",++cas);
if(flow>C)printf("possible\n");
else{
vector cut=solver.Mincut();
solver.Reduce();
vectorans;
for(int i=0;i=C)ans.push_back(e);
e.cap=temp;
}
if(ans.empty())printf("not possible\n");
else{
sort(ans.begin(),ans.end(),cmp);
printf("possible option:(%d,%d)",ans[0].from,ans[0].to);
for(int i=1;i
|