董晓算法代码

#include<bits/stdc++.h>
#define N 10010
#define M 200010
using namespace std;

int n,m,S,T;
int a[N],b[N],c;
struct edge{int v,c,ne;}e[M];
int h[N],idx=1; //从2,3开始配对
int d[N],cur[N],vis[N];

void add(int a,int b,int c){
  e[++idx]={b,c,h[a]};
  h[a]=idx;
}
bool bfs(){ //对点分层，找增广路
  memset(d,0,sizeof d);
  queue<int>q; 
  q.push(S); d[S]=1;
  while(q.size()){
    int u=q.front(); q.pop();
    for(int i=h[u];i;i=e[i].ne){
      int v=e[i].v;
      if(d[v]==0 && e[i].c){
        d[v]=d[u]+1;
        q.push(v);
        if(v==T)return true;
      }
    }
  }
  return false;
}
int dfs(int u, int mf){ //多路增广
  if(u==T) return mf;
  int sum=0;
  for(int i=cur[u];i;i=e[i].ne){
    cur[u]=i; //当前弧优化
    int v=e[i].v;
    if(d[v]==d[u]+1 && e[i].c){
      int f=dfs(v,min(mf,e[i].c));
      e[i].c-=f; 
      e[i^1].c+=f; //更新残留网
      sum+=f; //累加u的流出流量
      mf-=f;  //减少u的剩余流量
      if(mf==0)break;//余量优化
    }
  }
  if(sum==0) d[u]=0; //残枝优化
  return sum;
}
int dinic(){ //累加可行流
  int flow=0;
  while(bfs()){
    memcpy(cur, h, sizeof h);
    flow+=dfs(S,1e9);
  }
  return flow;
}
int main(){
  scanf("%d%d",&n,&m);
  S=1,T=n;
  for(int i=1;i<=m;i++){
    scanf("%d%d%d",&a[i],&b[i],&c);
    add(a[i],b[i],c); 
    add(b[i],a[i],0);
  }
  printf("%d ",dinic());

  //最小割的最少边数
  idx=1;
  memset(h,0,sizeof h);
  for(int i=1;i<=m;i++){
    add(a[i],b[i],1); 
    add(b[i],a[i],0);
  }
  printf("%d\n",dinic());  
  return 0;
}

重要提醒：

此题题面用的是洛谷的，但数据用的是官网的。洛谷删掉了很难的一个问：在最小割且割边数最少前提下，求字典序最小的割边的方案（一个方案里边是从小到大排序的），输出前两问后另起一行开始输出方案，每行一条边。

因此，在洛谷 AC 的代码在此无法通过，且很可能需要大改、重构才能解决被删掉的那一问。

此外，董晓在讲最小割的视频里讲了此题，但他求最小割割最少边的方案是错误的，不应把所有（原网络正向边）边权设为 1 再跑一次 dinic，而是把满流边设为 1 而把其它边设为正无穷，并且重新设置边权也有更简洁的做法。退流反向边边权应设为 0。

下面只贴能通过本题题面即能在洛谷 AC 的代码。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct nd{
	ll v,w,ne;
}e[2005];
int n,m,s,t,d[35],cur[35],h[35],idx=1;
void ad(int u,int v,int w){
	e[++idx]={v,w,h[u]};
	h[u]=idx;//链式前向星，最后存是头 
}
bool bfs(){
	for(int i=0;i<=n;i++)d[i]=0;
	queue<int>q;
	q.push(s);
	d[s]=1;
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int i=h[u];i;i=e[i].ne){
			int v=e[i].v;
			if(d[v]==0&&e[i].w){
				q.push(v);
				d[v]=d[u]+1;
				if(v==t)return true;
			}
		}
	}
	return false;
}
ll dfs(int u,ll mf){
	if(u==t)return mf;
	ll sum=0;
	for(int i=cur[u];i;i=e[i].ne){
		cur[u]=i;
		int v=e[i].v;
		if(d[v]==d[u]+1&&e[i].w){
			ll f=dfs(v,min(mf,e[i].w));
			e[i].w-=f,e[i^1].w+=f;
			sum+=f,mf-=f;
			if(mf==0)break;
		}
	}
	if(sum==0)d[u]=0;
	return sum;
}
ll din(){
	ll fl=0;
	while(bfs()){
		for(int i=0;i<=n;i++)cur[i]=h[i];//当前弧优化重置 
		fl+=dfs(s,2e10);
	}
	return fl;
}
int main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	s=1,t=n;
	int mm=m;
	while(mm--){
		int u,v,w;
		cin>>u>>v>>w;
		ad(u,v,w),ad(v,u,0);
	}
	cout<<din()<<' ';
	for(int i=1;i<=m;i++){
		if(e[i<<1].w==0)e[i<<1].w=1,e[(i<<1)^1].w=0;
		else e[i<<1].w=0ll+0x3f3f3f3f3f3f3f,e[(i<<1)^1].w=0;
	}
	cout<<din();
	return 0;
}