网络流

最大流最小割

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int inf=1e9;
int n,m,x,y,z,maxflow,deep[500];//deep深度 
struct Edge{
  int next,to,dis;
}edge[500];
int num_edge=-1,head[500],cur[500];//cur用于复制head 
queue <int> q;
void add_edge(int from,int to,int dis,bool flag)
{
  edge[++num_edge].next=head[from];
  edge[num_edge].to=to;
  if (flag) edge[num_edge].dis=dis;//反图的边权为 0
  head[from]=num_edge;
}
//bfs用来分层 
bool bfs(int s,int t)
{
  memset(deep,0x7f,sizeof(deep));
  while (!q.empty()) q.pop();
  for (int i=1; i<=n; i++) cur[i]=head[i];
  deep[s]=0;
  q.push(s);

  while (!q.empty())
  {
      int now=q.front(); q.pop();
      for (int i=head[now]; i!=-1; i=edge[i].next)
      {
          if (deep[edge[i].to]>inf && edge[i].dis)//dis在此处用来做标记 是正图还是返图 
          {
              deep[edge[i].to]=deep[now]+1;
              q.push(edge[i].to);
          }
      }
  }
  if (deep[t]<inf) return true;
  else return false;
}
//dfs找增加的流的量 
int dfs(int now,int t,int limit)//limit为源点到这个点的路径上的最小边权 
{
  if (!limit || now==t) return limit;

  int flow=0,f;
  for (int i=cur[now]; i!=-1; i=edge[i].next)
  {
      cur[now]=i;
      if (deep[edge[i].to]==deep[now]+1 && (f=dfs(edge[i].to,t,min(limit,edge[i].dis))))
      {
          flow+=f;
          limit-=f;
          edge[i].dis-=f;
          edge[i^1].dis+=f;
          if (!limit) break;
      }
  }
  return flow;
}
void Dinic(int s,int t)
{
  while (bfs(s,t))
      maxflow+=dfs(s,t,inf);
}
int main()
{
//  for (int i=0; i<=500; i++) edge[i].next=-1;
  memset(head,-1,sizeof(head));
  scanf("%d%d",&m,&n);
  for (int i=1; i<=m; i++)
  {
      scanf("%d%d%d",&x,&y,&z);
      add_edge(x,y,z,1);//正边
       add_edge(y,x,z,0);//反边
  }
  Dinic(1,n);
  printf("%d",maxflow);
  return 0;
}

最小费用最大流

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn=100010;
bool vis[maxn];
int n,m,s,t,x,y,z,f,dis[maxn],pre[maxn],last[maxn],flow[maxn],maxflow,mincost;
//dis最小花费;pre每个点的前驱；last每个点的所连的前一条边；flow源点到此处的流量 
struct Edge{
  int to,next,flow,dis;//flow流量 dis花费 
}edge[maxn];
int head[maxn],num_edge; 
queue <int> q;
void add_edge(int from,int to,int flow,int dis)
{
  edge[++num_edge].next=head[from];
  edge[num_edge].to=to;
  edge[num_edge].flow=flow;
  edge[num_edge].dis=dis;
  head[from]=num_edge;
}
bool spfa(int s,int t)
{
  memset(dis,0x7f,sizeof(dis));
  memset(flow,0x7f,sizeof(flow));
  memset(vis,0,sizeof(vis));
  q.push(s); vis[s]=1; dis[s]=0; pre[t]=-1;

  while (!q.empty())
  {
      int now=q.front();
      q.pop();
      vis[now]=0;
      for (int i=head[now]; i!=-1; i=edge[i].next)
      {
          if (edge[i].flow>0 && dis[edge[i].to]>dis[now]+edge[i].dis)//正边 
          {
              dis[edge[i].to]=dis[now]+edge[i].dis;
              pre[edge[i].to]=now;
              last[edge[i].to]=i;
              flow[edge[i].to]=min(flow[now],edge[i].flow);//
              if (!vis[edge[i].to])
              {
                  vis[edge[i].to]=1;
                  q.push(edge[i].to);
              }
          }
      }
  }
  return pre[t]!=-1;
}
void MCMF()
{
  while (spfa(s,t))
  {
      int now=t;
      maxflow+=flow[t];
      mincost+=flow[t]*dis[t];
      while (now!=s)
      {//从源点一直回溯到汇点 
          edge[last[now]].flow-=flow[t];//flow和dis容易搞混 
          edge[last[now]^1].flow+=flow[t];
          now=pre[now];
      }
  }
}
int main()
{
  memset(head,-1,sizeof(head)); num_edge=-1;//初始化 
  scanf("%d%d%d%d",&n,&m,&s,&t);
  for (int i=1; i<=m; i++)
  {
      scanf("%d%d%d%d",&x,&y,&z,&f);
      add_edge(x,y,z,f); add_edge(y,x,0,-f);
      //反边的流量为0，花费是相反数 
  }
  MCMF();
  printf("%d %d",maxflow,mincost);
  return 0;
}