[洛谷 1344][USACO4.4]Pollutant Control

题目链接

https://www.luogu.org/problem/P1344

题解

容易看出本题的目标是求出最小割，但如何确保在求得最小割的情况下割掉的边数最小呢？

考虑将边数这一要素加入到流量当中去。我们将原来每条边的流量乘上 \(1001\)，然后再加 \(1\)。

因为最多只有 \(1000\) 条边，这意味着：

1. 可以将答案的低位视为 \(1001\) 进制数，割掉的边数不会影响到最小割值的计算（即低位不会产生进位）；
2. 答案的高位即为最小割，低位为要割掉的边数。

#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
#define INF 0x3f3f3f3f
using namespace std;
struct edge
{
 int v,w,next;
}e[2005];
int head[35],cur[35],dist[35],vis[35],cnt=1,n,m;
void addedge(int u,int v,int w)
{
 e[++cnt].v=v;
 e[cnt].w=w;
 e[cnt].next=head[u];
 head[u]=cnt;
}
bool bfs()
{
 queue<int> q;
 memset(dist,INF,sizeof(dist));
 memcpy(cur,head,sizeof(head));
 dist[1]=0,vis[1]=1;
 q.push(1);
 while(!q.empty())
 {
  int u=q.front();
  q.pop();
  vis[u]=0;
  for(int i=head[u];i;i=e[i].next)
  {
   int v=e[i].v;
   if(e[i].w&&dist[v]>dist[u]+1)
   {
    dist[v]=dist[u]+1;
    if(!vis[v])
    {
     vis[v]=1;
     q.push(v);
    }
   }
  }
 }
 return dist[n]!=INF;
}
int dfs(int u,int flow)
{
 if(u==n)return flow;
 int used=0;
 for(int i=cur[u];i;i=e[i].next)
 {
  cur[u]=i;
  int v=e[i].v;
  if(e[i].w&&dist[v]==dist[u]+1)
  {
   int w=dfs(v,min(flow-used,e[i].w));
   used+=w;
   e[i].w-=w;
   e[i^1].w+=w;
   if(used==flow)break;
  }
 }
 return used;
}
int main()
{
 cin>>n>>m;
 for(int i=1;i<=m;i++)
 {
  int u,v,w;
  cin>>u>>v>>w;
  addedge(u,v,w*1001+1);
  addedge(v,u,0);
 }
 long long ans=0;
 while(bfs())
  ans+=dfs(1,INF);
 cout<<ans/1001<<" "<<ans%1001<<endl;
 return 0;
}