标签归档:网络流

HDU – 6214 Smallest Minimum Cut

HDU 6214

求最小割的最小割边数量.
每边以w*(m+1)+1为边权加入图中,最小割为maxflow/(m+1),最小割的边数为maxflow%(m+1).
精髓在于将已选边数加到了流量信息里.

#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <stack>
#include <utility>
using namespace std;
const int INF = 1e9;
const int maxn = 1e6;

struct Edge{
  int from,to,cap,flow;
  Edge(int u,int v,int c,int f):from(u),to(v),cap(c),flow(f){}
};

struct Dinic{
  int n,m,s,t;
  vector<Edge> edges;
  vector<int> G[maxn];
  bool vis[maxn];
  int d[maxn];
  int cur[maxn];

  void init(int n){
    for(int i=0;i<=n;++i) G[i].clear();
    edges.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 s,int t){
    this->s=s;
    this->t=t;
    int flow=0;
    while(BFS()){
      memset(cur,0,sizeof(cur));
      flow+=DFS(s,INF);
    }
    return flow;
  }

} flow;

int main() {
  // freopen("in.txt","r",stdin);
  // freopen("out.txt","w",stdout);
   int T,n,m;
   scanf("%d",&T);
   while(T--){
     scanf("%d%d",&n,&m);
     int s,t;
     scanf("%d%d",&s,&t);
     flow.init(n);
     for(int i=0;i<m;++i){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        flow.AddEdge(u,v,w*(m+1)+1);
        flow.AddEdge(v,u,0);
     }
     printf("%d\n",flow.Maxflow(s,t)%(m+1));

   }
   return 0;
}