bzoj1520poi2006szk-schools

关键词：

Description

Input

Output

Sample Input

Sample Output

HINT

Source

很裸的费用流

#include <bits/stdc++.h>
#define ll long long
#define inf 1e9+10
using namespace std;
inline int read()
	int x=0;int f=1;char ch=getchar();
	while(!isdigit(ch)) if(ch==‘-‘) f=-1;ch=getchar();
	while(isdigit(ch)) x=x*10+ch-‘0‘;ch=getchar();
	return x*f;
 
const int MAXN=1e5+10;
struct node
	int y,next,back,flow,w;
e[MAXN];
int linkk[MAXN],len=0,vis[405],dis[405],s,t,n,ans=0;
inline void insert(int x,int y,int f,int c)
	e[++len].y=y;e[len].next=linkk[x];linkk[x]=len;e[len].back=len+1;e[len].flow=f;e[len].w=c;
	e[++len].y=x;e[len].next=linkk[y];linkk[y]=len;e[len].back=len-1;e[len].flow=0;e[len].w=-c;

inline bool getdis()
	memset(dis,10,sizeof(dis));
	memset(vis,0,sizeof(vis));
	dis[t]=0;vis[t]=1;
	deque<int>q;q.push_front(t);
	while(!q.empty())
		int tn=q.front();q.pop_front();
		for(int i=linkk[tn];i;i=e[i].next)
			if(e[e[i].back].flow&&dis[e[i].y]>dis[tn]-e[i].w)
				dis[e[i].y]=dis[tn]-e[i].w;
				if(!vis[e[i].y])
					if(!q.empty()&&dis[q.front()]>dis[e[i].y]) q.push_front(e[i].y);
					else q.push_back(e[i].y);vis[e[i].y]=1;
				
			
		
		vis[tn]=0;
	
	return dis[s]<168430090;

inline int getcost(int x,int flow)
	int f=0,d;vis[x]=1;
	if(x==t) return flow;
	for(int i=linkk[x];i;i=e[i].next)
		if(!vis[e[i].y]&&e[i].flow&&dis[e[i].y]==dis[x]-e[i].w)
			if(d=getcost(e[i].y,min(e[i].flow,flow-f)))
				f+=d;e[i].flow-=d;e[e[i].back].flow+=d;
				ans+=e[i].w*d;if(f==flow) return flow;
			
		
	
	return f;

inline int zkw()
	int sum=0;
	while(getdis())
		vis[t]=1;
		while(vis[t])
			memset(vis,0,sizeof(vis));
			sum+=getcost(s,inf);
		
	
	return sum;

int main()
	n=read();s=0;t=2*n+1;
	for(int i=1;i<=n;i++)
		int m=read();int x=read();int y=read();int k=read();
		for(int j=x;j<=y;j++)
			insert(i,j+n,1,abs(m-j)*k);
		
		insert(s,i,1,0);
		insert(i+n,t,1,0);
	
	int sum=zkw();
	if(sum==n) cout<<ans<<endl;
	else cout<<"NIE"<<endl;
	return 0;

bzoj1520[poi2006]szk-schoolskm算法

【BZOJ1520】[POI2006]Szk-SchoolsDescriptionInputOutput如果有可行解,输出最小代价,否则输出NIE.SampleInput5112311513255415103331SampleOutput9题解：二分图最小权匹配裸题，可以直接无脑费用流，不过这里就当复习一下KM算法了。#include<cstdio>#inclu... 查看详情

p3440[poi2006]szk-schools（费用流）(代码片段)

P3440[POI2006]SZK-Schools每所学校$i$开一个点，$link(S,i,1,0)$每个编号$j$开一个点，$link(i,T,1,0)$蓝后学校向编号连边，$link(i,j,1,val)$最后跑一遍费用流如果没有满流就是$NIE$否则就是最小代价了#include<iostream>#include<cstdio>#include<... 查看详情

bzoj1510[poi2006]kra-thedisks*

bzoj1510[POI2006]Kra-TheDisks题意：一个瓶子有n个节，每个节有一个宽度。现在要从上往下扔m个盘子，如果盘子的下一个位置宽度比该盘子的宽度小则盘子会停在这个位置。问最后一个盘子会停在那个位置。n，m≤300000。题解：首先利... 查看详情

[bzoj1510][poi2006]kra-thedisks_暴力

Kra-TheDisksbzoj-1510POI-2006题目大意：题目链接。注释：略。想法：不难发现其实只有前缀最小值是有效的。进而我们把盘子一个一个往里放，弄一个自底向上的指针往上蹦即可。时间复杂度$O(n)$。Code：#include<iostream>#include<cst... 查看详情

[bzoj1513][poi2006]tet-tetris3d

[BZOJ1513][POI2006]Tet-Tetris3D试题描述Task:Tetris3D"Tetris"游戏的作者决定做一个新的游戏,一个三维的版本,在里面很多立方体落在平面板,一个立方体开始落下直到碰上一个以前落下的立方体或者落地即停止.作者想改变一下游戏的目的使... 查看详情

bzoj1513:[poi2006]tet-tetris3d

Description三维空间从上落下几个长方体,问最后的最高高度.Solution二维线段树.感觉这种东西是可以yy出来的吧..对行建线段树,再对列建线段树维护行的信息,注意打标记的位置,和返回的时候一定要记得统计上标记.开4倍内存会MLE...Co... 查看详情

bzoj1513[poi2006]tet-tetris3d二维线段树

【BZOJ1513】[POI2006]Tet-Tetris3DDescriptionTask:Tetris3D"Tetris"游戏的作者决定做一个新的游戏,一个三维的版本,在里面很多立方体落在平面板,一个立方体开始落下直到碰上一个以前落下的立方体或者落地即停止.作者想改变一下游戏的目的... 查看详情

bzoj1511:[poi2006]okr-periodsofwordskmp(代码片段)

n-ne[n]是n的最长循环节长度，其实就是n-最短前缀=后缀长度然后我们要求最短循环节，其实就是ne一直往前跳，跳到不能跳为止，这时的n-ne[n]就是n的最短循环节长度#include<iostream>#include<cstdio>usingnamespacestd;constintN=1000005;in... 查看详情

bzoj1513[poi2006]tet-tetris3d(代码片段)

二维线段树板子，注意标记永久化。1#include<bits/stdc++.h>2usingnamespacestd;3intans,A,B,n,ql,qr,qd,qu;4structQuerx56intv[3005],tag[3005];7voidchange(intk,intl,intr,intL,intR,intw)89v[k]=max(v[k],w);10if(l==L&a 查看详情

bzoj1513[poi2006]tet-tetris3d二维线段树

题目链接BZOJ1513题解真正地理解了一波线段树标记永久化的姿势每个节点维护两个值\(v\)和\(tag\)\(v\)代表儿子中的最值\(tag\)代表未下传的最值显然节点的区间大于等于\(v\)的实际区间而\(tag\)的区间包含节点的区间我们在修改的时... 查看详情

bzoj1513:[poi2006]tet-tetris3d

DescriptionTask:Tetris3D"Tetris"游戏的作者决定做一个新的游戏,一个三维的版本,在里面很多立方体落在平面板,一个立方体开始落下直到碰上一个以前落下的立方体或者落地即停止.作者想改变一下游戏的目的使得它更大众化,在新游戏... 查看详情

bzoj1513[poi2006]tet-tetris3d（二维线段树）

 【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=1513 【题目大意】　　一个立方体开始落下直到碰上一个以前落下的立方体或者落地即停止.　　你将知道落下的立方体信息以及位置,　　你的任务就是回答所有立方... 查看详情

bzoj1511[poi2006]okr-periodsofwordskmp-next数组

原文地址：http://www.cnblogs.com/GXZlegend/p/6827027.html题目描述一个串是有限个小写字符的序列,特别的,一个空序列也可以是一个串.一个串P是串A的前缀,当且仅当存在串B,使得A=PB.如果PA并且P不是一个空串,那么我们说P是A的一个proper前缀... 查看详情

bzoj1515[poi2006]lis-thepostman有向图欧拉回路(代码片段)

LINK：Lis-ThePostman看完题觉得虽然容易发现是有向图欧拉回路但是觉得很难解决这个问题。先分析一下有向图的欧拉回路：充要条件图中每个点的入度-出度=0且整张图是一个强连通分量。证明：首先考虑前者这个思想是从一个点出... 查看详情

[poi2006]ork-ploughing

[POI2006]ORK-Ploughinghttps://www.luogu.org/problemnew/show/P3444题目描述(Byteasar)想耕种他那块矩形的田,他每次能耕种矩形的一边(上下左右都行),在他每次耕完后,剩下的田也一定是矩形,每块小区域边长为(1),耕地的长宽分别为(m)和(n),不幸的是(... 查看详情

bzoj2428:[haoi2006]均分数据

二次联通门: BZOJ2428:[HAOI2006]均分数据    /*BZOJ2428:[HAOI2006]均分数据模拟退火初体验完全随机化算法估计对我这种非酋来说的话估计是用处不大了吧23333*/#include<cstdio>#include<iostream>#include<cstdlib>#incl 查看详情

[bzoj2527][poi2011]meteors

2527:[Poi2011]MeteorsTimeLimit:60Sec  MemoryLimit:128MBSubmit:1807  Solved:646[Submit][Status][Discuss]DescriptionByteotianInterstellarUnion(BIU)hasrecentlydiscoveredanewplanetinan 查看详情

bzoj2213[poi2011]differencedp

【BZOJ2213】[Poi2011]DifferenceDescriptionAwordconsistingoflower-caselettersoftheEnglishalphabet(‘a‘-‘z‘)isgiven.Wewouldliketochooseanon-emptycontiguous(i.e.one-piece)fragmentofthewordsoastomaximisethed 查看详情