首页 > 代码库 > BZOJ1520: [POI2006]Szk-Schools
BZOJ1520: [POI2006]Szk-Schools
1520: [POI2006]Szk-Schools
Time Limit: 5 Sec Memory Limit: 64 MBSubmit: 342 Solved: 173
[Submit][Status]
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
HINT
Source
题解:
裸的最小费用最大流。。。
代码:
1 #include<cstdio> 2 3 #include<cstdlib> 4 5 #include<cmath> 6 7 #include<cstring> 8 9 #include<algorithm> 10 11 #include<iostream> 12 13 #include<vector> 14 15 #include<map> 16 17 #include<set> 18 19 #include<queue> 20 21 #include<string> 22 23 #define inf 1000000000 24 25 #define maxn 500+100 26 27 #define maxm 250000 28 29 #define eps 1e-10 30 31 #define ll long long 32 33 #define pa pair<int,int> 34 35 #define for0(i,n) for(int i=0;i<=(n);i++) 36 37 #define for1(i,n) for(int i=1;i<=(n);i++) 38 39 #define for2(i,x,y) for(int i=(x);i<=(y);i++) 40 41 #define for3(i,x,y) for(int i=(x);i>=(y);i--) 42 43 #define mod 1000000007 44 45 using namespace std; 46 47 inline int read() 48 49 { 50 51 int x=0,f=1;char ch=getchar(); 52 53 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 54 55 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();} 56 57 return x*f; 58 59 } 60 int n,m,k,mincost,maxflow,tot=1,s,t,head[maxn],q[maxm],d[maxn],from[2*maxm]; 61 62 bool v[maxn]; 63 64 struct edge{int from,next,go,v,c;}e[2*maxm]; 65 66 void ins(int x,int y,int z,int w) 67 68 { 69 70 e[++tot].go=y;e[tot].from=x;e[tot].v=z;e[tot].c=w;e[tot].next=head[x];head[x]=tot; 71 72 } 73 74 void insert(int x,int y,int z,int w) 75 76 { 77 78 ins(x,y,z,w);ins(y,x,0,-w); 79 80 } 81 82 bool spfa() 83 84 { 85 86 for (int i=s;i<=t;i++){v[i]=0;d[i]=inf;} 87 88 int l=0,r=1,y;q[1]=s;d[s]=0;v[0]=1; 89 90 while(l!=r) 91 92 { 93 94 int x=q[++l];if(l==maxn)l=0;v[x]=0; 95 96 for (int i=head[x];i;i=e[i].next) 97 98 if(e[i].v&&d[x]+e[i].c<d[y=e[i].go]) 99 100 {101 102 d[y]=d[x]+e[i].c;from[y]=i;103 104 if(!v[y]){v[y]=1;q[++r]=y;if(r==maxn)r=0;}105 106 }107 108 }109 110 return d[t]!=inf;111 112 }113 114 void mcf()115 116 {117 118 while(spfa())119 120 {121 122 int tmp=inf;123 124 for(int i=from[t];i;i=from[e[i].from]) tmp=min(tmp,e[i].v);125 126 mincost+=d[t]*tmp;maxflow+=tmp;127 128 for(int i=from[t];i;i=from[e[i].from]){e[i].v-=tmp;e[i^1].v+=tmp;}129 130 }131 132 }133 134 int main()135 136 {137 138 freopen("input2.txt","r",stdin);139 140 freopen("output3.txt","w",stdout);141 142 n=read();s=0;t=2*n+1;143 for1(i,n)144 {145 insert(s,i,1,0);insert(i+n,t,1,0);146 int x=read(),l=read(),r=read(),y=read();147 for2(j,l,r)insert(i,j+n,1,y*(abs(j-x)));148 }149 mcf();150 if(maxflow==n)printf("%d\n",mincost);else puts("NIE");151 152 return 0;153 154 }
BZOJ1520: [POI2006]Szk-Schools
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。