https://www.luogu.org/problemnew/solution/P2762
最小割对应的点, 在最后一次更新中 dinic 的 bfs 会把他的 dep 重置掉. 所以可以根据这个性质复原最小割.
- #include<bits/stdc++.h>
- using namespace std;
- #define ll long long
- /* dinic begin */
- const int MAXN=10100;
- const int MAXM=100010;
- const int INF=0x3f3f3f3f;
- struct Edge{
- int to,next,cap,flow;
- }edge[MAXM];
- int tol;
- int head[MAXN];
- void init(){
- tol=2;
- memset(head,-1,sizeof(head));
- }
- void addedge(int u,int v,int w){
- edge[tol].to=v;edge[tol].cap=w;edge[tol].flow=0;
- edge[tol].next=head[u];head[u]=tol++;
- edge[tol].to=u;edge[tol].cap=0;edge[tol].flow=0;
- edge[tol].next=head[v];head[v]=tol++;
- }
- int Q[MAXN];
- int dep[MAXN],cur[MAXN],sta[MAXN];
- bool bfs(int s,int t,int n){
- int front=0,tail=0;
- memset(dep,-1,sizeof(dep[0])*(n+1));
- dep[s]=0;
- Q[tail++]=s;
- while(front<tail){
- int u=Q[front++];
- for(int i=head[u];i!=-1;i=edge[i].next){
- int v=edge[i].to;
- if(edge[i].cap>edge[i].flow&&dep[v]==-1){
- dep[v]=dep[u]+1;
- if(v==t)
- return true;
- Q[tail++]=v;
- }
- }
- }
- return false;
- }
- int dinic(int s,int t,int n){
- //n 最后一个节点的编号的下一个编号
- int maxflow=0;
- while(bfs(s,t,n)){
- for(int i=0;i<n;i++)cur[i]=head[i];
- int u=s,tail=0;
- while(cur[s]!=-1){
- if(u==t){
- int tp=INF;
- for(int i=tail-1;i>=0;i--){
- tp=min(tp,edge[sta[i]].cap-edge[sta[i]].flow);
- }
- maxflow+=tp;
- for(int i=tail-1;i>=0;i--){
- edge[sta[i]].flow+=tp;
- edge[sta[i]^1].flow-=tp;
- if(edge[sta[i]].cap-edge[sta[i]].flow==0)
- tail=i;
- }
- u=edge[sta[tail]^1].to;
- }
- else if(cur[u]!=-1&&edge[cur[u]].cap>edge[cur[u]].flow
- &&dep[u]+1==dep[edge[cur[u]].to]){
- sta[tail++]=cur[u];
- u=edge[cur[u]].to;
- }
- else{
- while(u!=s&&cur[u]==-1){
- u=edge[sta[--tail]^1].to;
- }
- cur[u]=edge[cur[u]].next;
- }
- }
- }
- return maxflow;
- }
- /* dinic end */
- int m,n;
- int main(){
- init();
- scanf("%d%d",&m,&n);
- char buf[40000];
- fgets(buf,40000,stdin);
- int s=0,t=m+n+1;
- int sum=0;
- for(int i=1;i<=m;i++){
- fgets(buf,40000,stdin);
- stringstream ss(buf);
- int w;
- ss>>w;
- //cout<<w<<endl;
- sum+=w;
- addedge(s,i,w);
- int j;
- while(ss>>j){
- //cout<<j<<endl;
- addedge(i,j+m,INF);
- }
- }
- for(int i=1;i<=n;i++){
- int w;
- scanf("%d",&w);
- //cout<<"w="<<w<<endl;
- addedge(i+m,t,w);
- }
- int maxflow=dinic(s,t,t);
- vector<int> v1;
- for(int u=1;u<=m;u++){
- if(dep[u]!=-1){
- v1.push_back(u);
- // 最后一次 dinic 还有 dep 的边说明没有被割掉
- }
- }
- vector<int>v2;
- for(int u=1;u<=n;u++){
- if(dep[u+m]!=-1){
- v2.push_back(u);
- // 最后一次 dinic 还有 dep 的边说明没有被割掉
- }
- }
- for(int i=0;i<v1.size();i++){
- printf("%d%c",v1[i],"\n"[i==v1.size()-1]);
- }
- for(int i=0;i<v2.size();i++){
- printf("%d%c",v2[i],"\n"[i==v2.size()-1]);
- }
- printf("%d\n",sum-maxflow);
- }
来源: http://www.bubuko.com/infodetail-3004623.html