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 ;

}