2023CCPC女生赛-D-费用流
题目：https://codeforces.com/gym/104725/problem/D
金人巷可以看作一个$ n × m$ 的方格图，有些方格上有障碍物，另外有一些方格上有额外收益，还有一些方格上什么也没有。其中有 \(k\) 个方格是物流起点，另有 \(k\) 个方格是物流终点，保证这些方格上都没有障碍物，且这 \(2k\) 个方格互不相同，起点和终点没有对应关系。一条合法的物流，必须从一个物流起点开始，每次走到一个相邻（两个方格相邻当且仅当它们拥有公共边）的没有障碍物的方格，最终到一个物流终点结束。一条物流的初始评分为 100 分，每经过一个方格（物流经过的点包括起点和终点）扣 1 分，如果经过的方格上有额外收益，则给评分加 1 分。
由于物流所使用的机巧鸟不太聪明，所以任意两条物流都不允许经过同一个方格。请你合理进行物流规划，物流可以有任意条（一条都没有也是可以的），求出所有物流的评分总和的最大值。
\(n,m\leq 30,k\leq 10\)。
首先谴责一下 \(n,m,k\) 的数据范围只写最大值不写最小值= =
然后这题建图其实就是典中典，看完第一反应就是poj的一个题（翻博客是poj 3422）。
-
网格中的每个网格拆成两个点：一个入点、一个出点。
-
入点向出点连一条边，如果经过这个格子一次，就代表有 \(1\) 的流量，与之对应的在这里，就可能需要 \(1\) 或 \(0\) 的花费。
-
相邻的网格之间的连边，就相当于一个格子的出点连到另一个格子的入点，很显然容量是 \(1\) ，单位费用是 \(0\) 。
-
\(k\) 个关键点连接源点和汇点，容量依然是 \(1\) 。
-
最终一组流量为 \(x\) 的网络流，就对应着选择了 \(x\) 条物流，并且因为每条物流有 \(100\) 的收益，而单位费用都是 \(1\) ，即使走了最远的距离（\(30+30-1=59\)）收益依然是正的。也就是说，只要流量能变大，那么收益一定是变大的。所以自然就变成关心流量最大的情况下，最小费用是多少。
-
那就直接套个最小费用最大流（没懂为什么题解写的是可行流）：
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
const int N=30*30*2+15;
const int M=5*30*30+2*10+15;
const int INF=(~0u>>1);
namespace MCMF{
struct edge{
int to,nxt,w,c;//weight,cost
edge(int to=0,int nxt=0,int w=0,int c=0):to(to),nxt(nxt),w(w),c(c){}
}edges[M<<1];
int mx_node,s,t,cnt,ans,maxflow;
int head[N],vis[N],d[N],pre[N],infc[N];
deque<int>q;
void addEdge(int u,int v,int w,int c){
edges[++cnt]=edge(v,head[u],w,c);head[u]=cnt;
edges[++cnt]=edge(u,head[v],0,-c);head[v]=cnt;
}
#define cur edges[i].to
bool spfa(){
rep(i,1,mx_node)d[i]=INF,vis[i]=0;
infc[s]=INF;d[s]=0;q.push_front(s);vis[s]=1;
while(!q.empty()){
int k=q.front();q.pop_front();
vis[k]=0;
for(int i=head[k];i;i=edges[i].nxt)if(edges[i].w&&d[cur]>d[k]+edges[i].c){
d[cur]=d[k]+edges[i].c;
pre[cur]=i;infc[cur]=min(infc[k],edges[i].w);
if(!vis[cur]){
vis[cur]=1;
if(!q.empty()&&d[cur]<d[q.front()])q.push_front(cur);
else q.push_back(cur);
}
}
}
if(d[t]==INF)return 0;
return 1;
}
#undef cur
void update(){
int tmp=t;
while(tmp!=s){
int i=pre[tmp];
edges[i].w-=infc[t];
edges[i^1].w+=infc[t];
tmp=edges[i^1].to;
}
maxflow+=infc[t];
ans+=d[t]*infc[t];
}
void init(int _n){
cnt=1;
mx_node=_n;
}
int work(){
while(spfa())update();//MCMF
return 100*maxflow-ans;
}
};
const int MX=32;
int n,m,k,a[MX][MX],x[MX],y[MX],p[MX],q[MX];
int dx[]={0,1};
int dy[]={1,0};
int get_index(int i,int j,bool out){
if(!out)return (i-1)*m+j;
else return n*m+(i-1)*m+j;
}
int main(){
fastio;
cin>>n>>m>>k;
rep(i,1,n)rep(j,1,m)cin>>a[i][j];
rep(i,1,k)cin>>x[i]>>y[i];
rep(i,1,k)cin>>p[i]>>q[i];
//[1,nm],[nm+1,nm+nm],2nm+1,2nm+2
int ans=0;
MCMF::init(2*n*m+2);
int st=2*n*m+1,ed=2*n*m+2,mx=n*m;
MCMF::s=st;MCMF::t=ed;
rep(i,1,k){
MCMF::addEdge(st,get_index(x[i],y[i],0),1,0);
MCMF::addEdge(get_index(p[i],q[i],1),ed,1,0);
}
//2*10
rep(i,1,n)rep(j,1,m){
if(a[i][j]==0)MCMF::addEdge(get_index(i,j,0),get_index(i,j,1),1,1);
else if(a[i][j]==1)MCMF::addEdge(get_index(i,j,0),get_index(i,j,1),1,0);
//n*m+4*n*m=5*n*m
rep(t,0,1){
int tx=i+dx[t],ty=j+dy[t];
if(tx>n||ty>m)continue;
MCMF::addEdge(get_index(i,j,1),get_index(tx,ty,0),1,0);
MCMF::addEdge(get_index(tx,ty,1),get_index(i,j,0),1,0);
}
}
cout<<MCMF::work();
return 0;
}