Aizu 2304 Reverse Roads(无向流)

把有向图修改成无向图,并保证每条边的流量守恒并满足有向容量(即abs(flow(u,v) - flow(v,u)) <= 1)满足限制。

得到最大流,根据残流输出答案。

因为最后少了'\n'而WA...

#include<bits/stdc++.h>
using namespace std;
const int N = ,M = N*(N-);
int n,m;
int hd[N],nx[M],to[M],cap[M],ect; inline void addEdge(int u,int v,int c = )
{
nx[ect] = hd[u];
to[ect] = v;
cap[ect] = c;
hd[u] = ect++;
} int S,T;
int vis[N],clk;
int lv[N],q[N];
int cur[N]; bool bfs()
{
int l = ,r = ;
clk++;
q[r++] = S; vis[S] = clk; lv[S] = ;
while(l<r){
int u = q[l++];
for(int i = hd[u]; ~i; i = nx[i]){
int v = to[i];
if(vis[v] != clk && cap[i]> ){
vis[v] = clk;
lv[v] = lv[u]+;
q[r++] = v;
}
}
}
return vis[T] == clk;
} int aug(int u,int a)
{
if(u == T||!a) return a;
int flow = ,f;
for(int &i = cur[u]; ~i; i = nx[i]){
int v = to[i];
if(lv[v] == lv[u]+ && (f = aug(v,min(cap[i],a)))>){
cap[i] -= f; cap[i^] += f;
a -= f; flow += f;
if(!a) break;
}
}
return flow;
}
const int INF = 0x3f3f3f3f;
int MaxFlow()
{
int flow = ;
while(bfs()){
memcpy(cur,hd,sizeof(hd));
flow += aug(S,INF);
}
return flow;
} //#define LOCAL
int main()
{
#ifdef LOCAL
freopen("in.txt","r",stdin);
#endif
scanf("%d%d",&n,&m);
memset(hd,-,sizeof(hd));
for(int i = ; i < m; i++){
int u,v; scanf("%d%d",&u,&v);
addEdge(v,u);
addEdge(u,v);
}
scanf("%d%d",&S,&T);
printf("%d\n",MaxFlow());
vector<int> ans;
for(int i = ; i < m; i++){
if(!cap[i<<]) ans.push_back(i+);
}
printf("%d\n",(int)ans.size());
for(auto a:ans){
printf("%d\n",a);
}
return ;
}
上一篇:第一百七十二节,jQuery,动画效果


下一篇:Android开发之对ListView的数据进行排序