2 条题解
-
0
#include<bits/stdc++.h> using namespace std; const int N=2e4+10, M=3e5+10; struct edge{int x, y, f, pre;} a[M]; int alen, last[N]; void ins(int x, y, int f) { alen++; a[alen]=edge{x, y, f, last[x]}; last[x]=alen; alen++; a[alen]=edge{y, x, 0, last[y]}; last[y]=alen; } int n, m, T, st, ed, h[N], tsp, dfn[N], low[N], p[M], plen; bool v[N]; stack<int> sta; int scc[N], cnt; bool bfs() { queue<int> Q; Q.push(st); memset(h, 0, sizeof(h)); h[st]=1; while(!Q.empty()) { int x=Q.front(); Q.pop(); for(int k=last[x]; k; k=a[k].pre) if(a[k].f) { int y=a[k].y; if(!h[y]) { h[y]=h[x]+1; Q.push(y); } } } return (h[ed]>0); } int dinic(int x, int f) { if(x==ed) return f; int sx=0; for(int k=last[x]; k; k=a[k].pre) if(a[k].f) { int y=a[k].y; if(h[y]==(h[x]+1)) { int sy=dinic(y, min(a[k].f, f-sx)); a[k].f-=sy; a[k^1].f+=sy; sx+=sy; if(sx==f) return f; } } if(!sx) h[x]=0; return sx; } void tarjan(int x) { dfn[x]=low[x]=++tsp; sta.push(x); v[x]=1; for(int k=last[x]; k; k=a[k].pre) if(a[k].f) { int y=a[k].y; if(!dfn[y]) { tarjan(y); low[x]=min(low[x], low[y]); } else if(v[y]) low[x]=min(low[x], dfn[y]); } if(dfn[x]==low[x]) { int y; cnt++; do { y=sta.top(); sta.pop(); v[y]=0; scc[y]=cnt; } while(x!=y); } } int main() { scanf("%d%d%d", &n, &m, &T); st=n+m+1; ed=st+1; alen=1; memset(last, 0, sizeof(last)); for(int i=1; i<=T; i++) { int x, y; scanf("%d%d", &x, &y); ins(x, y+n, 1); } int tlen=alen; for(int i=1; i<=n; i++) ins(st, i, 1); for(int i=1; i<=m; i++) ins(i+n, ed, 1); int t=0; while(bfs()) t+=dinic(st, 1e9); tsp=0; memset(dfn, 0, sizeof(dfn)); memset(low, 0, sizeof(low)); cnt=0; memset(v, 0, sizeof(v)); memset(scc, 0, sizeof(scc)); for(int i=1; i<=n+m; i++) if(!dfn[i]) tarjan(i); plen=0; for(int i=2; i<=tlen; i+=2) { int x=a[i].x, y=a[i].y; if(a[i].f && scc[x]!=scc[y]) p[++plen]=i/2; } if(plen==0) {printf("0\n\n"); return 0;} printf("%d\n", plen); for(int i=1; i<=plen; i++) printf("%d ", p[i]); printf("\n"); return 0; } -
0
huangzheng
LV 6
@ 2025-10-8 16:57:11
#include<bits/stdc++.h> using namespace std; const int N=2e4+10, M=3e5+10; struct edge{int x, y, f, pre;} a[M]; int alen, last[N]; void ins(int x, int y, int f) { alen++; a[alen]=edge{x, y, f, last[x]}; last[x]=alen; alen++; a[alen]=edge{y, x, 0, last[y]}; last[y]=alen; } int n, m, T, st, ed, h[N], tsp, dfn[N], low[N], p[M], plen; bool v[N]; stack<int> sta; int scc[N], cnt; bool bfs() { queue<int> Q; Q.push(st); memset(h, 0, sizeof(h)); h[st]=1; while(!Q.empty()) { int x=Q.front(); Q.pop(); for(int k=last[x]; k; k=a[k].pre) if(a[k].f) { int y=a[k].y; if(!h[y]) { h[y]=h[x]+1; Q.push(y); } } } return (h[ed]>0); } int dinic(int x, int f) { if(x==ed) return f; int sx=0; for(int k=last[x]; k; k=a[k].pre) if(a[k].f) { int y=a[k].y; if(h[y]==(h[x]+1)) { int sy=dinic(y, min(a[k].f, f-sx)); a[k].f-=sy; a[k^1].f+=sy; sx+=sy; if(sx==f) return f; } } if(!sx) h[x]=0; return sx; } void tarjan(int x) { dfn[x]=low[x]=++tsp; sta.push(x); v[x]=1; for(int k=last[x]; k; k=a[k].pre) if(a[k].f) { int y=a[k].y; if(!dfn[y]) { tarjan(y); low[x]=min(low[x], low[y]); } else if(v[y]) low[x]=min(low[x], dfn[y]); } if(dfn[x]==low[x]) { int y; cnt++; do { y=sta.top(); sta.pop(); v[y]=0; scc[y]=cnt; } while(x!=y); } } int main() { scanf("%d%d%d", &n, &m, &T); st=n+m+1; ed=st+1; alen=1; memset(last, 0, sizeof(last)); for(int i=1; i<=T; i++) { int x, y; scanf("%d%d", &x, &y); ins(x, y+n, 1); } int tlen=alen; for(int i=1; i<=n; i++) ins(st, i, 1); for(int i=1; i<=m; i++) ins(i+n, ed, 1); int t=0; while(bfs()) t+=dinic(st, 1e9); tsp=0; memset(dfn, 0, sizeof(dfn)); memset(low, 0, sizeof(low)); cnt=0; memset(v, 0, sizeof(v)); memset(scc, 0, sizeof(scc)); for(int i=1; i<=n+m; i++) if(!dfn[i]) tarjan(i); plen=0; for(int i=2; i<=tlen; i+=2) { int x=a[i].x, y=a[i].y; if(a[i].f && scc[x]!=scc[y]) p[++plen]=i/2; } if(plen==0) {printf("0\n\n"); return 0;} printf("%d\n", plen); for(int i=1; i<=plen; i++) printf("%d ", p[i]); printf("\n"); return 0; }
- 1
