Vexoben
Nov 25, 2017
题目链接：http://codevs.cn/problem/1227
周六zrf要讲网络流啊，像我这种蒟蒻不预习一下肯定全程掉线。
题解
首先是一种建模的思想：将每个点拆成出入两个点。
取k次，相当于流出一条大小为k的流。流过一个点即将这个点的数取走。
因为每个点可以流经多次，但只能产生一次贡献，所以我们从所有入点向所有出点连一条容量为1的边，价值为点的权值。然后将出入点都向右边和下方的点的入点连一条容量为inf，价值为0的边，跑最小费用最大流即可。
几个细节：
1、有两个源点两个汇点。建立超级源汇点即可。注意(n,n)的入点到汇点容量应为k-1，出点到汇点容量为1。
2、要求的实际是最大费用。将所有边费用取反即可。
3、STL的dequeue好慢啊手写一个
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<time.h>
#include<vector>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#define LL long long
using namespace std;
const int N=1e5+10;
const int mod=1e9+7;
const int inf=0x3f3f3f3f;
int n,m,k,s,t,V,E=1,cost,a[51][51];
int fir[N],len[N],dis[N],nex[N],arr[N],vis[N],cap[N];
struct Dequeue{
int head,tail,num[N<<1];
inline void Init() {head=N-1,tail=N;}
inline int size() {return head-tail+1;}
inline void push_front(int x) {num[++head]=x;}
inline void push_back(int x) {num[--tail]=x;}
inline void pop_front() {--head;}
inline void pop_back() {++tail;}
inline int front() {return num[head];}
inline int back() {return num[tail];}
}q;
inline void read(int &x) {
int f=1; x=0;
register char c=getchar();
for (;(c!='-')&&(c<'0'||c>'9');) c=getchar();
if (c=='-') f=-1,c=getchar();
for (;c>='0'&&c<='9';c=getchar()) x=x*10+c-'0';
x*=f;
}
inline void Add_Edge(int x,int y,int c,int l) {
nex[++E]=fir[x];
fir[x]=E; arr[E]=y;
len[E]=l; cap[E]=c;
nex[++E]=fir[y];
fir[y]=E; arr[E]=x;
len[E]=-l; cap[E]=0;
}
inline void Build_Graph() {
V=1;
Add_Edge(1,2,k,0);
for (int i=1;i<=n;++i)
for (int j=1;j<=n;++j) {
V+=2;
Add_Edge(V-1,V,1,-a[i][j]);
if (j!=n) {
Add_Edge(V-1,V+1,inf,0);
Add_Edge(V,V+1,inf,0);
}
if (i!=n) {
Add_Edge(V-1,V+2*n-1,inf,0);
Add_Edge(V,V+2*n-1,inf,0);
}
}
Add_Edge(V-1,V+1,k-1,0);
Add_Edge(V,V+1,1,0);
++V;
}
inline int Spfa() {
q.Init();
memset(vis,0,sizeof(int)*(V+5));
memset(dis,0x3f,sizeof(int)*(V+5));
dis[t]=0; q.push_front(t);
while (q.size()) {
int u=q.front(); q.pop_front();
vis[u]=0;
for (int i=fir[u];i;i=nex[i]) {
if (!cap[i^1]) continue;
int v=arr[i];
if (dis[v]>dis[u]+len[i^1]) {
dis[v]=dis[u]+len[i^1];
if (!vis[v]) {
vis[v]=1;
if (dis[q.front()]>dis[v]) q.push_front(v);
else q.push_back(v);
}
}
}
}
return dis[s]<inf;
}
inline int Dfs(int x,int maxflow) {
vis[x]=1;
if (x==t||!maxflow) return maxflow;
int ans=0;
for (int i=fir[x];i;i=nex[i]) {
if(cap[i]&&!vis[arr[i]]&&dis[x]==dis[arr[i]]+len[i]) {
int del=Dfs(arr[i],min(maxflow,cap[i]));
maxflow-=del;
ans+=del; cost+=del*len[i];
cap[i]-=del; cap[i^1]+=del;
}
}
return ans;
}
int main() {
read(n); read(k);
for (int i=1;i<=n;++i)
for (int j=1;j<=n;++j)
read(a[i][j]);
Build_Graph();
s=1,t=V;
while (Spfa()) {
do {
memset(vis,0,sizeof(int)*(V+10));
Dfs(s,inf);
}while (vis[t]);
}
printf("%d",-cost);
return 0;
}