「BZOJ1520」[POI2006] Szk – Schools
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
1 1 2 3
1 1 5 1
3 2 5 5
4 1 5 10
3 3 3 1
Sample Output
9
题解
这个裸的费用流吧。。正好复习下zkw
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 |
#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=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,cnt=1,T,tot,ans; int last[405],h[405],q[405],d[405]; bool inq[405]; struct data{int to,next,c,v;}e[100005]; 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,0,-c); } bool spfa() { memset(inq,0,sizeof(inq)); int head=0,tail=1; for(int i=0;i<=T;i++)d[i]=inf; q[0]=T;d[T]=0;inq[T]=1; while(head!=tail) { int now=q[head];head++;if(head==405)head=0; for(int i=last[now];i;i=e[i].next) if(e[i^1].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]=1; q[tail]=e[i].to; tail++;if(tail==405)tail=0; } } inq[now]=0; } return d[0]!=inf; } int dfs(int x,int f) { inq[x]=1; if(x==T)return f; int used=0,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^1].v+=w; used+=w;if(used==f)return f; } return used; } void zkw() { while(spfa()) { inq[T]=1; while(inq[T]) { memset(inq,0,sizeof(inq)); tot+=dfs(0,inf); } } } int main() { n=read();T=2*n+1; for(int i=1;i<=n;i++)insert(0,i,1,0); for(int i=1;i<=n;i++)insert(i+n,T,1,0); for(int i=1;i<=n;i++) { int m=read(),a=read(),b=read(),k=read(); for(int j=a;j<=b;j++) insert(i,n+j,1,abs((j-m)*k)); } zkw(); if(tot!=n)puts("NIE"); else printf("%d\n",ans); return 0; } |
计数器 9328079
OI 课件=>
OI 课件=>
为什么zkw会有spfa啊，而且这不是spfa暴力改嘛？