[POI2006]SZK-Schools

[POI2006]SZK-Schools

luogu

#include<bits/stdc++.h>
using namespace std;
const int N=405,M=1e5+5;
int re(){
	int x=0,w=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
	return x*w;
}
int n,s,t,cnt=1,flow,ans;
int h[N],d[N],id[N],p[N];
queue<int>q;bool vis[N];
struct edge{int to,next,f,w;}e[M];
void link(int u,int v,int w){
	e[++cnt]=(edge){v,h[u],1,w};h[u]=cnt;
	e[++cnt]=(edge){u,h[v],0,-w};h[v]=cnt;
}
bool spfa(){
	memset(d,63,sizeof(d));
	q.push(s);d[s]=0;vis[s]=1;
	while(!q.empty()){
		int u=q.front();q.pop();vis[u]=0;
		for(int i=h[u];i;i=e[i].next){
			int v=e[i].to;
			if(d[v]>d[u]+e[i].w&&e[i].f){
				d[v]=d[u]+e[i].w;p[v]=u;id[v]=i;
				if(!vis[v])vis[v]=1,q.push(v);
			}
		}
	}
	if(d[t]==d[t+1])return 0;
	for(int i=t;i!=s;i=p[i])
		e[id[i]].f--,e[id[i]^1].f++;
	flow++;ans+=d[t];return 1;
}
int main(){
	n=re();t=2*n+1;
	for(int i=1,m,l,r,k;i<=n;i++){
		m=re(),l=re(),r=re(),k=re();
		link(s,i,0),link(i+n,t,0);
		for(int j=l;j<=r;j++)link(i,j+n,k*abs(m-j));
	}
	while(spfa());
	if(flow^n)puts("NIE");
	else printf("%d
",ans);
	return 0;
}