NOI2012美食节

动态加点减少常数的（不加当前弧还是要T的）费用流。

#include<bits/stdc++.h>
#define maxn 105 * 805
#define inf 0x3f3f3f3f
using namespace std;

int n,m;
int info[maxn],buf[maxn],Prev[maxn<<1],to[maxn<<1],cap[maxn<<1],cst[maxn<<1],cp[45],t[45][105],hd[105],blst[maxn],cnt_e=1,cnt; 
void Node(int u,int v,int c,int ct){ Prev[++cnt_e]=info[u],info[u]=cnt_e,buf[u]=cnt_e,to[cnt_e]=v,cap[cnt_e]=c,cst[cnt_e]=ct; }
void Line(int u,int v,int c,int ct){ Node(u,v,c,ct),Node(v,u,0,-ct); }
int S,T,dist,dis[maxn],inq[maxn],vis[maxn];
bool SPFA(){
	for(int i=1;i<=cnt;i++) dis[i] = inf;
	queue<int>q;
	dis[T] = 0;q.push(T);
	for(int u;!q.empty();){
		u = q.front() , q.pop();inq[u] = 0;
		for(int i=info[u];i;i=Prev[i])
			if(cap[i^1] && dis[to[i]] > dis[u] + cst[i^1]){
				dis[to[i]] =dis[u] + cst[i^1];
				if(!inq[to[i]]) inq[to[i]] = 1 , q.push(to[i]);
			}
	}
	return dis[S] < inf;
}
int aug(int u,int mx){
	if(u == T){
		dist += mx * dis[S];
		return mx;
	}
	int st = mx , inc;vis[u] = 1;
	for(int &i=info[u];i;i=Prev[i])
		if(cap[i] && dis[u] == dis[to[i]] + cst[i] && !vis[to[i]]){
			inc = aug(to[i] , min(st , cap[i]));
			st -= inc , cap[i] -= inc , cap[i^1] += inc;
			if(!st) break;
		}
	vis[u] = 0;
	return mx - st;
}

int main(){
	scanf("%d%d",&n,&m);
	S = ++cnt , T = ++cnt;
	for(int i=1,a;i<=n;i++){
		scanf("%d",&a);
		Line(S,cp[i]=++cnt,a,0);
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			scanf("%d",&t[i][j]);
	for(int j=1;j<=m;j++){
		blst[++cnt] = j , ++hd[j];
		for(int i=1;i<=n;i++)
			Line(cp[i],cnt,1,t[i][j]);
		Line(cnt,T,1,0);
	}
	for(;SPFA();){
		int stm = aug(S,inf);
		for(int i=1;i<=cnt;i++) info[i] = buf[i];
		for(int i=info[T];i;i=Prev[i])
			if(cap[i] && blst[to[i]]){
				int j = blst[++cnt] = blst[to[i]];
				blst[to[i]] = 0;
				++hd[j];
				for(int k=1;k<=n;k++)
					Line(cp[k],cnt,1,t[k][j] * hd[j]);
				Line(cnt,T,1,0);
			}
	}
	printf("%d\n",dist);
}