![[原博客] POI系列(1)](https://image.shishitao.com:8440/aHR0cHM6Ly9ia3FzaW1nLmlrYWZhbi5jb20vdXBsb2FkL2NoYXRncHQtcy5wbmc%2FIQ%3D%3D.png?!?w=700&webp=1 "[原博客] POI系列(1)")
正规、严谨、精妙。 -POI
发现POI(波兰信息学奥赛)的题都很有意思。于是开刷bzoj上的poi题目(按ac人数降序。。)。顺手写一写题解，加深印象。
为了防止一篇文章过于长，打算每五道题另起一篇文章。
BZOJ 1103 : [POI2007]大都市meg
给一棵树，每次可以把树上的一些边标记了，问一个点与根之间需要走多少没有标记的边。
这个可以把这颗树遍历得到一个dfs序每第一次经过一个点的时候记录为+1,第二次经过一个点的时候记录为-1，然后记录每个点第一次经过时在序列里的位置f[i]和第二次经过在序列里的位置l[i]，对于查询（x）就是序列中一直到f[x]-1的前缀和，因为真正没走的那些边都+1-1消掉了，只剩下真正要统计的边了。对于每次标记(a,b) 设a<b 就是序列里 f[b]的位置-1，l[b]的位置+1，就相当于消掉了这条边。另外这道题得手写栈dfs，否则会爆栈。
/**************************************************************
Problem: 1103
User: zrts
Language: C++
Result: Accepted
Time:4484 ms
Memory:9596 kb
****************************************************************/
#include<cstdio>
#include<cstring>
#include<algorithm>
#define lowbit(x) (x&-x)
//by zrt
//problem:
using namespace std;
typedef long long ll;
);
int n,m;
];
],P[],X[],tot;
],l[];
];
int tim;
],top;
void add(int pos,int x){
for(;pos<=n;pos+=lowbit(pos)){
c[pos]+=x;
}
}
int ask(int pos){
;
;pos-=lowbit(pos)){
ret+=c[pos];
}
return ret;
}
inline void Add(int x,int y){
P[++tot]=y;X[tot]=H[x];H[x]=tot;
}
int main(){
#ifdef LOCAL
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
scanf("%d",&n);
,x,y;i<n;i++){
scanf("%d%d",&x,&y);
if(x<y) Add(x,y);
else Add(y,x);
}
stk[top++]=;
int k;
){
k=stk[--top];
if(f[k]){
l[k]=++tim;
c[tim]=-;
continue;
}else{
f[k]=++tim;
c[tim]=;
stk[top++]=k;
for(int i=H[k];i;i=X[i]){
stk[top++]=P[i];
}
continue;
}
}
n*=;
;i<n;i++){
if(i+lowbit(i)<=n){
c[i+lowbit(i)]+=c[i];
}
}
scanf("%d",&m);
m=n/+m-;
,x,y;i<m;i++){
scanf("%s",s);
]=='W'){
scanf("%d",&x);
printf();
}else{
scanf("%d%d",&x,&y);
if(x>y){
add(f[x],-);
add(l[x],);
}else{
add(f[y],-);
add(l[y],);
}
}
}
;
}
BZOJ 1121 : [POI2008]激光发射器SZK
刚看完觉得不可做。
因为光线都是沿45°，所以从一个点发射光线必有一个点接收，又因为光路是可逆的，不可能有不同的点出发的光路重合的现象，所以输出n/2（原题让输出方案。。）;
/**************************************************************
Problem: 1121
User: zrts
Language: C++
Result: Accepted
Time:0 ms
Memory:804 kb
****************************************************************/
#include<cstdio>
#include<cstring>
#include<algorithm>
//by zrt
//problem:
using namespace std;
typedef long long ll;
);
int main(){
#ifdef LOCAL
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
int n;
scanf("%d",&n);
printf();
;
}
BZOJ 1113 : [Poi2008]海报PLA
显然单调栈啊，相等的时候处理一下。没了。
/**************************************************************
Problem: 1113
User: zrts
Language: C++
Result: Accepted
Time:1496 ms
Memory:1780 kb
****************************************************************/
#include<cstdio>
#include<cstring>
#include<algorithm>
//by zrt
//problem:
using namespace std;
typedef long long ll;
);
],top;
int main(){
#ifdef LOCAL
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
int n;
scanf("%d",&n);
;
,x;i<n;i++){
scanf("%*d%d",&x);
&&x<=stk[top-]) {
top--,ans++;
if(stk[top]==x) ans--;
}
stk[top++]=x;
}
printf("%d\n",ans+top);
;
}
BZOJ 1529 : [POI2005]ska Piggy banks
一堆存钱罐，每个存钱罐的钥匙在另一个存钱罐里，问最少砸烂多少个存钱罐。
如果A罐的钥匙在B罐里，我们连边B->A，表示只要开了B就能开A。然后得到一张无向图，显然在一个强连通分量中的罐子最多只用砸烂一个，而每个强连通分量的罐子有可能被别的强连通分量的罐子打开，所以将这张图缩点，得到一个DAG，显然我们只用砸那些入度为0的强连通分量并且每个分量砸一个就ok了，也就是DAG的叶子节点。
（原来tarjan中，dfn没有记录的必要啊，详见程序。）
/**************************************************************
Problem: 1529
User: zrts
Language: C++
Result: Accepted
Time:2316 ms
Memory:63620 kb
****************************************************************/
#include<cstdio>
#include<cstring>
#include<algorithm>
//by zrt
//problem:
using namespace std;
typedef long long ll;
);
int n;
],X[],P[],tot;
inline void add(int x,int y){
P[++tot]=y;X[tot]=H[x];H[x]=tot;
}
],stk[],top;
];
int cnt;
];
void tarjan(int x){
int dfn=low[x]=++tim;
instack[x]=;stk[top++]=x;
for(int i=H[x];i;i=X[i]){
if(!low[P[i]]) tarjan(P[i]),low[x]=min(low[x],low[P[i]]);
else if(instack[P[i]]) low[x]=min(low[x],low[P[i]]);
}
if(low[x]==dfn){
cnt++;
int k;
do{
k=stk[--top];
instack[k]=;
belong[k]=cnt;
}while(k!=x);
}
}
];
int main(){
#ifdef LOCAL
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
scanf("%d",&n);
,x;i<=n;i++){
scanf("%d",&x);
add(x,i);
}
;i<=n;i++){
if(!low[i]) tarjan(i);
}
;i<=n;i++){
for(int j=H[i];j;j=X[j]){
;
}
}
;
;i<=cnt;i++){
if(!ind[i]) ot++;
}
printf("%d\n",ot);
;
}
BZOJ 1532 : [POI2005]Kos-Dicing
网络流里这个模型太熟了。
首先求最大值最小先二分，然后判定是否可以相互制约使得都在ans场内决出冠军。具体连边就是S向每场比赛连边容量为1，每场比赛向两个人分别连边，容量1。然后每个人向T连边，容量为ans。看看最大流S是否满载。搞定。
/**************************************************************
Problem: 1532
User: zrts
Language: C++
Result: Accepted
Time:576 ms
Memory:2764 kb
****************************************************************/
#include<cstdio>
#include<cstring>
#include<algorithm>
//by zrt
//problem:
using namespace std;
typedef long long ll;
);
int n,m;
],X[],P[],flow[],d[],tot;
],h,t;
],b[];
int S,T;
inline void add(int x,int y,int z){
P[++tot]=y;X[tot]=H[x];H[x]=tot;flow[tot]=z;
}
bool bfs(){
memset(d,,;
d[S]=;q[t++]=S;
int k;
while(h!=t){
k=q[h++];
for(int i=H[k];i;i=X[i]){
&&(!d[P[i]])){
q[t++]=P[i];
d[P[i]]=d[k]+;
}
}
}
return d[T];
}
int dfs(int x,int a){
||x==T) return a;
int f=a,tmp;
for(int i=H[x];i&&a;i=X[i]){
&&flow[i]>){
tmp=dfs(P[i],min(a,flow[i]));
a-=tmp;
flow[i]-=tmp;
flow[i^]+=tmp;
}
}
;
return f-a;
}
int dinic(){
);
while(bfs()){
f+=dfs(S,<<);
}
return f;
}
bool judge(int x){
memset(H,,;
;i<m;i++){
add(S,i,);add(i,S,);
add(i,a[i]+m,);add(a[i]+m,i,);
add(i,b[i]+m,);add(b[i]+m,i,);
}
;i<=n;i++) add(i+m,T,x),add(T,i+m,);
if(dinic()>=m) return true;
else return false;
}
int main(){
#ifdef LOCAL
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
scanf("%d%d",&n,&m);
;i<m;i++){
scanf("%d%d",&a[i],&b[i]);
}
),R(m),M;
S=,T=;
){
M=(L+R)>>;
if(judge(M)){
R=M;
}else L=M;
}
printf("%d\n",R);
;
}
以上。