牛客练习赛30E(国政议事)

链接：https://ac.nowcoder.com/acm/contest/216/E
思路：关于二分图必须匹配问题，看这里，引用一下：https://blog.csdn.net/element_hero/article/details/82845931
事实上对于匈牙利算法中不完备匹配我们可能需要额外建图（还没怎么想懂后面我用匈牙利算法再写一遍），事实上用网络流的话不需要重新建图，只需要在残留网络上跑一边tarjan边双即可，但注意要思考清楚跑tarjan的时候哪些边可以走，我一开始就是随便抄了一下一直不对，网上也没人用我这种图的表示方法，后面我认真思考了一下，对于u，v有流量，那么反向边可以跑而正向边不能跑，如果u，v没流量那么正向边可以跑而反向边不能跑，其实根本不用重新建图，概括起来也就一句话e.cap-e.flow>0时可以跑，否则不行。最后对于所有已经匹配的边检查一下是否属于一个强连通分量，如果属于则是可行边，否则是必须边。
代码：

#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;

const int maxn = 1001;
const int INF = 1e9;

struct edge{
    int from,to,cap,flow;
};

    int n,m,s,t,q;
    vector<edge> edges;
    vector<int> G[maxn],RG[maxn];
    bool vis[maxn];
    int d[maxn];
    int cur[maxn];

    vector<int> bcc[maxn];//强连通分量
    int dfn[maxn];
    int low[maxn];
    int scount[maxn];//是否为割点
    int sccno[maxn];//属于哪一个强连通分量
    int ntime;
    int bcc_cnt;
    deque<int> P;

    void init(){
        edges.clear();
        for(int i=0;i<=n;i++)G[i].clear();
    }

    void addedge(int from,int to,int cap){
        edges.push_back(edge{from,to,cap,0});
        edges.push_back(edge{to,from,0,0});
        m = edges.size();
        G[from].push_back(m-2);
        G[to].push_back(m-1);
    }

    bool bfs(){
        memset(vis,0,sizeof(vis));
        queue<int> q;
        q.push(s);
        d[s] = 0;
        vis[s] = 1;
        while(!q.empty()){
            int x = q.front();
            q.pop();
            for(int i=0;i<G[x].size();i++){
                edge &e = edges[G[x][i]];
                if(!vis[e.to]&&e.cap>e.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];i<G[x].size();i++){
            edge &e = edges[G[x][i]];
            if(d[x] + 1 == d[e.to]&&(f=dfs(e.to,min(a,e.cap-e.flow)))>0){
                e.flow+=f;
                edges[G[x][i]^1].flow -=f;
                flow+=f;
                a-=f;
                if(a==0)break;
            }
        }
        return flow;
    }

    int maxflow(){
        int flow = 0;
        while(bfs()){
            memset(cur,0,sizeof(cur));
            flow+=dfs(s,INF);
        }
        return flow;
    }

 void tarjan(int u){
    dfn[u] = low[u] = ++ntime;
    P.push_back(u);
    for(int i=0;i<G[u].size();i++){
        edge &e = edges[G[u][i]];
        if(e.cap-e.flow==0)continue;//一定要注意这里的判断！！！！因为写法不同所以这里判断的写法也不同！！！
        int v = e.to;
        if(!dfn[v]){
        tarjan(v);
        low[u] = min(low[u],low[v]);
        }
        else if(!sccno[v]){
            low[u] = min(low[u],dfn[v]);
        }
    }
    if(low[u]==dfn[u]){
        bcc_cnt++;
        int tmp;
        do{
            tmp = P.back();
            P.pop_back();
            sccno[tmp] = bcc_cnt;
            scount[bcc_cnt]++;//计算连通块所含的点数
        }while(tmp!=u);
    }
}

void find_bcc(){
    memset(sccno,0,sizeof(sccno));
    memset(dfn,0,sizeof(dfn));
    memset(scount,0,sizeof(scount));
    ntime = bcc_cnt = 0;
    for(int i=0;i<=2*n+1;++i)if(!dfn[i])tarjan(i);
}

int main(){
    scanf("%d%d",&n,&q);
    s = 0;
    t = 2*n+1;
    init();
    for(int i=0;i<q;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        addedge(a,b+n,1);
    }
    for(int i=1;i<=n;i++)addedge(s,i,1),addedge(i+n,t,1);
    int res = maxflow();
    printf("%d ",res);
    find_bcc();
    vector<int> ans;
    for(int i=0;i<q*2;i+=2){
        edge e = edges[i];
        if(e.flow&&sccno[e.from]!=sccno[e.to])ans.push_back(i/2+1);
    }
    sort(ans.begin(),ans.end());
    printf("%d\n",ans.size());
    for(int i=0;i<ans.size();i++){
        printf("%d\n",ans[i]);
    }   
    return 0;
}

补充一下删边的做法，对于匹配边我们删除之后再跑匈牙利算法，如果答案不变就不是必须边，否则就是必须边。
代码：

#include<bits/stdc++.h>
using namespace std;

const int maxn = 2000;

//注意编号从1开始
vector<int> G[maxn],RG[maxn];
bool vis[maxn];
int link[maxn];
int relink[maxn];
int m,s,t,q;
int nx,ny;
int dfn[maxn];
int low[maxn];
int sccno[maxn];
int scount[maxn];
int ntime;
int bcc_cnt;//连通块数量
int nowi = -1;
deque<int> P;

    struct edge{
        int from,to;
    };

    vector<edge> edges;

    void init(int nx,int ny){
        for(int i=0;i<=nx+ny+2;i++)G[i].clear();
    }

    inline void addedge(int from,int to){
        edges.push_back(edge{from,to});
        q = edges.size();
        G[from].push_back(q-1);
    }

    bool dfs(int u){
        vis[u] = 1;
        for(int i=0;i<G[u].size();i++){
            if(G[u][i]==nowi)continue;
            edge e = edges[G[u][i]];
            int v = e.to;
            if(!vis[v]){
                vis[v] = 1;
                if(link[v]==-1||dfs(link[v])){
                    link[v] = u;
                    return true;
                }
            }
        }
        return false;
    }

    int hungrey(){
        int res = 0;
        memset(link,-1,sizeof(link));
        for(int i=1;i<=nx;i++){
            memset(vis,0,sizeof(vis));
            if(dfs(i))res++;
        }
        return res;
    }

int main(){
    scanf("%d%d",&nx,&m);
    ny = nx;
    init(nx,ny);
    for(int i=1;i<=m;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        v+=nx;
        addedge(u,v);
    }
    int res = hungrey();
    for(int i=nx+1;i<=nx+ny;i++){
        relink[i] = link[i];  
    }
    printf("%d ",res);
    vector<int> ans;
    for(int i=0;i<m;i++){
        nowi = i;
        int u = edges[i].from;
        int v = edges[i].to;
        if(relink[v]!=u)continue;
        int now = hungrey();
        if(now!=res)ans.push_back(i+1);
    }
    printf("%d\n",ans.size());
    for(int i=0;i<ans.size();i++){
        printf("%d\n",ans[i]);
    }
    return 0;
}