Archive

Posts Tagged ‘图论’

NOIP2010提高组初赛问题求解第三题推广

October 27, 2010 Leave a comment

我们很自然地想求解下面的问题:

题目:记T为一队列,初始时为空,现有k个总和不超过n的正整数依次入列。如果无论这些数具体为何值,都能找到一种出队的方式,使得存在某个时刻队列T中的数之和恰好为m,那么k的最小值是___________。

显然当m<=0或n<=0或n<m时此题无解,否则:

类似地我们构建下面的图:

0—m—2m—…—m*[n/m]
1—m+1—2m+1—..—m*[n/m]+1
……
n%m—m+n%m—…—n

n%m+1—n%m+1+m—…—n-m+1

m-1—2m-1—…—n-n%m+1
第0行至第n%m行最多总共选([[n/m]/2]+1)(n%m+1)个
第n%m+1行至第m-1行最多总共选[([n/m]+1)/2](m-1-n%m)个
所以总共最多选([[n/m]/2]+1)(n%m+1)+[([n/m]+1)/2](m-1-n%m)个
注意到,我们计算的时候包含了S0,所以k的最小值就是([[n/m]/2]+1)(n%m+1)+[([n/m]+1)/2](m-1-n%m)

以原题n=32, m=9代入,得

k=([32/9]/2+1)*(32%9+1)+[(32/9]+1)/2]*(9-1-32%9)=2*6+2*3=18

Categories: OI Tags: , , , , ,

NOIP2010提高组初赛问题求解第三题解答

October 26, 2010 2 comments

题目:记T为一队列,初始时为空,现有n个总和不超过32的正整数依次入列。如果无论这些数具体为何值,都能找到一种出队的方式,使得存在某个时刻队列T中的数之和恰好为9,那么n的最小值是___________。

答案:18

证明:设这些数依次为a1, a2, a3, …, an,且记Si为前i项和,规定S0=0。很明显Si单调递增,且对任意i有0<=Si<=32。

我们可以以Si为顶点构造一张图,两点Si,Sj间连边当且仅当|Si-Sj|=9(图中数字为Si的编号,即i):

0–9–18–27
1–10–19–28
2–11–20–29
3–12–21–30
4–13–22–31
5–14–23–32
6–15–24
7–16–25
8–17–26

我们从这个图中选择一些顶点,将它们的编号排序作为一个可能的序列,比如选择0, 1, 10, 2, 13, 16,

排序后得0, 1, 2, 10, 13, 16,作差得ai依次为

1,1,8,3,3

显然有a2+a3=9 即满足条件

可以发现,若我们选择了图中的两个顶点,且它们之间连边,那么就存在一个和为9的子序列

那么,倘若对于某个n,我们能从图中选择n个顶点,使得任意两点间没有边,那么这个n就是不满足条件的

事实上,我们最多可以选择18个顶点,使得它们之间没有边相连:

第0行~第5行每行可以选第一、三个顶点或第二、四个顶点 最多共选10个

第6行~第8行每行可以选第一、三个顶点 最多选8个

注意到S0=0是必须选的,那么也就是说不满足条件的n的最大值是17

由鸽巢原理,若我们选择18个顶点,必有2个顶点之间有边连接,即必存在一个子序列的和为9

所以答案就是18。

Categories: OI Tags: , , ,

NOI 2008 志愿者招募

July 28, 2010 Leave a comment

这题竟然在省赛第3天中出现,要是当时有多做点NOI原题就好了

以样例来分析,设X[i]为第i类志愿者的人数,那么可得到约束为

Day[1]=X[1]>=2

Day[2]=X[1]+X[2]>=3

Day[3]=X[2]+X[3]>=4

添加辅助变量Y,将其化为等式得

Day'[1]=X[1]-Y[1]=2

Day'[2]=X[1]+X[2]-Y[2]=3

Day'[3]=X[2]+X[3]-Y[3]=4

添加第0、第4个等式,相邻等式两两相减(下减上)得

P[1]=X[1]-Y[1]=2

P[2]=X[2]+Y[1]-Y[2]=1

P[3]=X[3]+Y[2]-X[1]-Y[3]=1

P[4]=Y[3]-X[2]-X[3]=-4

进一步转化等式得

2-X[1]+Y[1]=0

1-X[2]-Y[1]+Y[2]=0

1-X[3]-Y[2]+X[1]+Y[3]=0

-4-Y[3]+X[2]+X[3]=0

分析上面四个等式,每个X[i]、Y[i]一正一负恰出现一次,若以每个等式为网络流中的顶点,上式就是流量守恒的形式

现规定以正为入,负为出,则对于每个P[i]:

若右端常数为正,从源点向该等式连边,容量为常数值,费用为0

若右端常数为负,从该等式向汇点连边,容量为常数值绝对值,费用为0

对于每个X[i],从它的正系数项出现的等式向负系数项出现的等式连边,容量为无穷大,费用为C[i]

对于每个Y[i],从它的正系数项出现的等式向负系数项出现的等式连边,容量为无穷大,费用为0

求最小费用最大流即为答案

#include<stdio.h> #include<string.h> #include<stdlib.h> #define MAXN 20001 #define QMAX 20001 #define MAXE 100001 #define oo 0x77777777 struct Edge{     int v,w,p;     Edge *next,*pair; } *edge[MAXN],*fe[MAXN],mempool[MAXE]; int S,T,memnum,dis[MAXN],Que[MAXN],vis[MAXN], Closed,Open,Size,ft[MAXN],ans; inline int min(int a, int b){     return a<b?a:b; } void add(int s, int t, int w, int p){     Edge *x=&mempool[memnum++],*y=&mempool[memnum++];     x->v=t,x->w=w,x->p=p,x->next=edge[s],x->pair=y,edge[s]=x;     y->v=s,y->w=0,y->p=-p,y->next=edge[t],y->pair=x,edge[t]=y; } int spfa(){     memset(dis,0x77,sizeof(dis));     memset(vis,0,sizeof(vis));     memset(ft,0,sizeof(ft));     memset(fe,0,sizeof(fe));     Closed=0,Open=0,Size=1,Que[0]=S,vis[S]=1,dis[S]=0;     while(Size){         int now=Que[Closed];         vis[now]=0,--Size,Closed=(Closed+1)%QMAX;         for(Edge *tmp=edge[now];tmp;tmp=tmp->next){             if(tmp->w>0){                 if(dis[now]+tmp->p<dis[tmp->v]){                     dis[tmp->v]=dis[now]+tmp->p;                     ft[tmp->v]=now;                     fe[tmp->v]=tmp;                     if(!vis[tmp->v]){                         ++Size;                         vis[tmp->v]=1;                         if(!Size||dis[tmp->v]<dis[Que[Closed]]){                             Closed=(Closed-1+QMAX)%QMAX;                             Que[Closed]=tmp->v;                         }else{                             Open=(Open+1)%QMAX;                             Que[Open]=tmp->v;                         }                     }                 }             }         }     }     return dis[T]<oo; } void aug(){     int delta=oo;     for(int i=T;i!=S;i=ft[i]){         if(fe[i]->w<delta){             delta=fe[i]->w;         }     }     for(int i=T;i!=S;i=ft[i]){         fe[i]->w-=delta,fe[i]->pair->w+=delta,ans+=delta*fe[i]->p;     } } int main(){     int N,M,x,y=0,s,t,c;     freopen("1.in","r",stdin);     freopen("1.out","w",stdout);     scanf("%d%d",&N,&M);     S=0,T=N+2;     for(int i=1;i<=N;++i){         scanf("%d",&x);         t=x-y;         if(t>0){             add(S,i,t,0);         }else{             add(i,T,-t,0);         }         y=x;         add(i+1,i,oo,0);     }     add(N+1,T,x,0);     for(int i=1;i<=M;++i){         scanf("%d%d%d",&s,&t,&c);         add(s,min(N+1,t+1),oo,c);     }     while(spfa())         aug();     printf("%d\n",ans);     return 0; }
Categories: OI Tags: , , , ,

poj 1144

July 28, 2010 Leave a comment

这题是求割点,参考《图论的算法与程序设计》中的算法即可

提供两个数据

1.in
21
17 4 18
1 11
7 5
13 1
3 1
14 5
15 20
9 12
6 8
16 14
18 8
8 4
20 18 10
2 3
12 5
5 9 20
19 20 9 11 2
11 3
4 15
10 3
21 3
0

1.out
6

2.in
63
30 11 33 52 9 25 47 28 59 29 32 18 7 35
51 15
19 47 25
32 27
9 46
7 59
13 53
35 17
6 2
63 21 35
52 40
4 58
27 61
43 54
49 16
11 44
25 57
60 54
21 35
23 41 50 11 2 25 3
59 1
33 41 15
53 57
22 62
57 19
34 7
44 46 39 57
48 29 3
47 48
18 29 25
10 38
62 25
56 23 8 62 46 30 6 44 43 60 29 45 26
3 6
40 12 31
38 45 22
8 11 43 13 49 18
14 49
55 10
5 49
28 3 14 61 20 24
54 35
29 5
46 31
45 44
17 54 19
39 61 58 2 26
61 37
1 52 58
12 62 31 56 43 28 61
36 12
58 44
26 29
31 3
50 52 6 28
16 10 51 25
20 54 47 13 29 4 6 44 52 32 53 39 57 3
42 48
0

2.out
7

#include<stdio.h> #include<string.h> #define MAXN 101 #define MAXE 20001 struct Edge{     int v;     Edge *next; } *edge[MAXN],mempool[MAXE]; int flag,n,snum,memnum,stack[MAXN],dfn[MAXN], low[MAXN],vis[MAXN],app[MAXN],ans; inline int min(int a, int b){     return a<b?a:b; } void add(int u, int v){     Edge *e=&mempool[memnum++];     e->v=v,e->next=edge[u],edge[u]=e; } int getn(){     int res=0;char ch;     for(ch=getchar();'0'<=ch&&ch<='9';ch=getchar())         res=res*10+ch-'0';     if(ch=='\n') flag=1;     return res; } void dfs(int now, int f){     stack[++snum]=now;     low[now]=dfn[now]=snum;     vis[now]=1;     int c=0;     for(Edge *i=edge[now];i;i=i->next){         if(i->v!=f){             if(vis[i->v]){                 low[now]=min(low[now],dfn[i->v]);             }else{                 ++c;                 dfs(i->v,now);                 low[now]=min(low[now],low[i->v]);                 if(f&&low[i->v]>=dfn[now]&&!app[now]){                     ++ans;                     app[now]=1;                 }             }         }     }     if(!f&&c>1&&!app[now]) ++ans; } void init(){     memnum=0;     ans=0;     snum=0;     memset(edge,0,sizeof(edge));     memset(app,0,sizeof(app));     memset(vis,0,sizeof(vis));     memset(dfn,0,sizeof(dfn));     memset(low,0,sizeof(low)); } int main(){     int now,t;     while(scanf("%d\n",&n)!=EOF){         if(!n) break;         init();         while(now=getn()){             if(!now) break;             flag=0;             while(t=getn()){                 add(now,t);                 add(t,now);                 if(flag) break;             }         }         if(n<=2) printf("0\n");         else{             dfs(1,0);             printf("%d\n",ans);         }     }     return 0; }
Categories: OI Tags: , , ,