[POI2006]Szk-Schools

[POI2006]Szk-Schools

Time Limit:5000MS Memory Limit:65536K
Total Submit:34 Accepted:21
Case Time Limit:1000MS

Description

Input

Output

如果有可行解, 输出最小代价,否则输出NIE.

Sample Input

Sample Output

Source
费用流TLE。。只好学了个KM算法来对付这题囧。。

#include <vector>#include <algorithm>#include <utility>#include <iostream>#include <cstdio>#include <cmath>#include <cstdlib>#include <cstring>#define rep(i,n) for(int i=0;i<n;i++)#define pb push_back#define Debug(x) cout<<#x<<"="<<x<<endl;#define For(i,l,r) for(int i=l;i<=r;i++)const int inf=~0U>>2,maxn=200;using namespace std;typedef long long ll;typedef unsigned long long ull;int Lx[maxn],Ly[maxn],w[maxn][maxn],Link[maxn],Slack[maxn],n;bool VisX[maxn],VisY[maxn];bool Find(int x){ VisX[x]=true; rep(y,n)if(!VisY[y]) { int t=Lx[x]+Ly[y]-w[x][y]; if(!t) { VisY[y]=true; if(Link[y]==-1||Find(Link[y])) return Link[y]=x,true; } else Slack[y]=min(Slack[y],t); } return false;}void KM(){ memset(Link,-1,sizeof Link); rep(i,n)Lx[i]=-inf; memset(Ly,0,sizeof Ly); rep(i,n)rep(j,n)Lx[i]=max(Lx[i],w[i][j]); rep(x,n) { rep(y,n)Slack[y]=inf; for(;;) { memset(VisX,0,sizeof VisX); memset(VisY,0,sizeof VisY); if(Find(x))break; int d=inf; rep(y,n)if(!VisY[y])d=min(d,Slack[y]); rep(x,n)if(VisX[x])Lx[x]-=d; rep(y,n)if(VisY[y])Ly[y]+=d;else Slack[y]-=d; } }}void InIt(){ cin>>n;int m,a,b,k; rep(x,n)rep(y,n)w[x][y]=-inf; rep(x,n) { scanf("%d%d%d%d",&m,&a,&b,&k);–a;–b;–m; for(int y=a;y<=b;y++) w[x][y]=-abs(y-m)*k; }}int main(){ //freopen("in","r",stdin); InIt();KM();int ans=0; rep(i,n) { int tmp; if((tmp=w[Link[i]][i])==-inf){cout<<"NIE"<<endl;return 0;} ans-=tmp; } cout<<ans<<endl;}951 1 2 31 1 5 13 2 5 54 1 5 103 3 3 1

2 thoughts on “[POI2006]Szk-Schools

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>