bzoj 1520 [POI2006]Szk-Schools 费用流

[POI2006]Szk-Schools

Time Limit: 5 Sec  Memory Limit: 64 MB
Submit: 743  Solved: 381
[Submit][Status][Discuss]

Description

Input

Output

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

Sample Input

5
1 1 2 3
1 1 5 1
3 2 5 5
4 1 5 10
3 3 3 1

Sample Output

9

HINT

 

考虑数据范围应该就是比较裸的费用流吧

 #include<iostream>

 #include<cstdio>

 #include<cstdlib>

 #include<algorithm>

 #include<cmath>

 #include<cstring>

 #include<set>

 #include<queue>

 #include<map>

 #define pa pair<int,int>

 #define mod 1000000007

 #define inf 1000000000

 #define ll long long

 using namespace std;

 int read()

 {

     int x=,f=;char ch=getchar();

     while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

     return x*f;

 }

 int n,cnt=,T,tot,ans;

 int last[],h[],q[],d[];

 bool inq[];

 struct data{int to,next,c,v;}e[];

 void ins(int u,int v,int w,int c)

 {

     e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[cnt].v=w;e[cnt].c=c;

 }

 void insert(int u,int v,int w,int c)

 {

     ins(u,v,w,c);

     ins(v,u,,-c);

 }

 bool spfa()

 {

     memset(inq,,sizeof(inq));

     int head=,tail=;

     for(int i=;i<=T;i++)d[i]=inf;

     q[]=T;d[T]=;inq[T]=;

     while(head!=tail)

     {

         int now=q[head];head++;if(head==)head=;

         for(int i=last[now];i;i=e[i].next)

             if(e[i^].v&&d[now]-e[i].c<d[e[i].to])

             {

                 d[e[i].to]=d[now]-e[i].c;

                 if(!inq[e[i].to])

                 {

                     inq[e[i].to]=;

                     q[tail]=e[i].to;

                     tail++;if(tail==)tail=;

                 }

             }

         inq[now]=;

     }

     return d[]!=inf;

 }

 int dfs(int x,int f)

 {

     inq[x]=;

     if(x==T)return f;

     int used=,w;

     for(int i=last[x];i;i=e[i].next)

         if(!inq[e[i].to]&&e[i].v&&d[x]-e[i].c==d[e[i].to])

         {

             w=f-used;

             w=dfs(e[i].to,min(e[i].v,w));

             ans+=w*e[i].c;

             e[i].v-=w;e[i^].v+=w;

             used+=w;if(used==f)return f;

         }

     return used;

 }

 void zkw()

 {

     while(spfa())

     {

         inq[T]=;

         while(inq[T])

         {

             memset(inq,,sizeof(inq));

             tot+=dfs(,inf);

         }

     }

 }

 int main()

 {

     n=read();T=*n+;

     for(int i=;i<=n;i++)insert(,i,,);

     for(int i=;i<=n;i++)insert(i+n,T,,);

     for(int i=;i<=n;i++)

     {

         int m=read(),a=read(),b=read(),k=read();

         for(int j=a;j<=b;j++)

             insert(i,n+j,,abs((j-m)*k));

     }

     zkw();

     if(tot!=n)puts("NIE");

     else printf("%d\n",ans);

     return ;

 }