CodeVS 1028 花店橱窗布置 【费用流】

tonyfang posted @ 2015年9月10日 10:15 in codevs with tags c++ OI , 251 阅读

注意要求最大值,所以边权取反,最后答案取反即可。

$O(???)$(我不会估算费用流的复杂度……反正可过)

 

# include <stdio.h>
# include <string.h>
# include <queue>
# include <algorithm>
using namespace std;
int F,V;
int a[101][101];
const int Max=80010;
int tot=1,head[Max],next[Max],to[Max],flow[Max],w[Max],S,T;
inline void add(int u,int v,int fl,int wx) {
	tot++;next[tot]=head[u];head[u]=tot;to[tot]=v;flow[tot]=fl,w[tot]=wx;
	tot++;next[tot]=head[v];head[v]=tot;to[tot]=u;flow[tot]=0,w[tot]=-wx;
}
queue<int> q;
bool vis[Max];
int d[Max],ans;
int pre[Max];
inline bool spfa() {
	memset(vis,0,sizeof(vis));
	while(!q.empty()) q.pop();
	memset(d,10300023,sizeof(d));
	vis[S]=1,q.push(S),d[S]=0;
	while(!q.empty()) {
		int top=q.front();q.pop();
		vis[top]=0;
		for (int i=head[top];i;i=next[i]) {
			if(d[top]+w[i]<d[to[i]]&&flow[i]) {
				d[to[i]]=d[top]+w[i];
				pre[to[i]]=i;
				if(!vis[to[i]]) {
					vis[to[i]]=1;
					q.push(to[i]);
				}
			}
		}
	}
	if(d[T]>=10300023) return false;
	return true;
}
inline void mincost() {
	int xm=1e9;
	for (int i=pre[T];i;i=pre[to[i^1]]) xm=min(xm,flow[i]);
	for (int i=pre[T];i;i=pre[to[i^1]]) {
		flow[i]-=xm;
		flow[i^1]+=xm;
		ans+=xm*w[i];
	}
}
int main() {
	scanf("%d%d",&F,&V);
	for (int i=1;i<=F;++i) 
		for (int j=1;j<=V;++j) scanf("%d",&a[i][j]);
	S=0,T=F+V+2;
	for (int i=1;i<=F;++i) {
		add(S,i,1,0);
		for (int j=1;j<=V;++j) add(i,j+F,1,-a[i][j]);
	}
	for (int i=1;i<=V;++i) add(i+F,T,1,0);
	while(spfa()) mincost();
	printf("%d\n",-ans);
	return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter