C++博客-Better man

zoj 1268

SHFACM — Fri, 06 Feb 2009 09:04:00 GMT

终于遇见了一个水题了
起初没有考虑到森林的情况

1 //0 0也是树
2 //有且只有一个顶点入度为0，其它顶点入度必须为一
3 #include<iostream>
4 using namespace std;
5 int in[100];
6 int hash[1000];
7 bool visit[1000];
8 int main()
9 {
10       int a,b,cas=1;
11       while(scanf("%d%d",&a,&b)&&a>=0&&b>=0)
12       {
13             memset(visit,0,sizeof(visit));
14             memset(hash,0,sizeof(hash));
15             memset(in,0,sizeof(in));
16             if(a==0&&b==0)
17             {
18                   printf("Case %d is a tree.\n",cas++);
19                   continue;
20             }
21             int m=1;
22             hash[++hash[0]]=a;
23             visit[a]=visit[b]=1;
24             hash[++hash[0]]=b;
25             in[b]++;
26             bool flag=0;
27             while(scanf("%d%d",&a,&b)&&a&&b)
28             {
29                   ++m;
30                   if(!visit[a])
31                         hash[++hash[0]]=a;
32                   if(!visit[b])
33                         hash[++hash[0]]=b;
34                   visit[a]=visit[b]=1;
35                   if(++in[b]>1)
36                   {
37                         flag=1;
38                         printf("Case %d is not a tree.\n",cas++);
39                   }
40             }
41             if(flag)continue;
42             else
43             {
44                   if(hash[0]-1!=m)
45                   {
46                         printf("Case %d is not a tree.\n",cas++);
47                         continue;
48                   }
49                   int root;
50                   bool flag=1;
51                   for(int i=1;i<=hash[0];++i)
52                         if(in[hash[i]]==0)
53                         {
54                               flag=0;
55                               root=i;
56                               break;
57                         }
58                   if(flag)
59                   {
60                         printf("Case %d is not a tree.\n",cas++);
61                         continue;
62                   }
63                   for(int i=1;i<=hash[0];++i)
64                         if(i!=root&&in[hash[i]]!=1)
65                         {
66                               printf("Case %d is not a tree.\n",cas++);
67                               continue;
68                         }
69                   printf("Case %d is a tree.\n",cas++);
70             }
71       }
72       return 0;
73 }

SHFACM 2009-02-06 17:04 发表评论

zoj 1055

SHFACM — Fri, 06 Feb 2009 07:47:00 GMT

这题其实很简单可是我却写超时了
其实题意就是求出一个点到另一个点的最短路径的个数：可以用bfs的性质求出
增加连个二维数组
一个表示从起点到当前点所需的部数
另一个表示到达当前的最小路径数
如果
当前点步数+1==下个点的步数
那么下个点的最小路径数+=当前点的最小路径数
这样做就不会超时了，速度很快

SHFACM 2009-02-06 15:47 发表评论

图的最小路径覆盖（zoj1525）

SHFACM — Thu, 05 Feb 2009 06:36:00 GMT

在一个ＰＸＰ的有向图中，路径覆盖就是在图中找一些路经，使之覆盖了图中的所有顶点，且任何一个顶点有且只有一条路径与之关联；（如果把这些路径中的每条路径从它的起始点走到它的终点，那么恰好可以经过图中的每个顶点一次且仅一次）；如果不考虑图中存在回路，那么每每条路径就是一个弱连通子集．

由上面可以得出：

１.一个单独的顶点是一条路径；

２．如果存在一路径p1,p2,......pk，其中p1 为起点，pk为终点，那么在覆盖图中，顶点p1,p2,......pk不再与其它的顶点之间存在有向边．

最小路径覆盖就是找出最小的路径条数，使之成为Ｐ的一个路径覆盖．

路径覆盖与二分图匹配的关系：

最小路径覆盖＝｜Ｐ｜－最大匹配数；

其中最大匹配数的求法是把Ｐ中的每个顶点pi分成两个顶点pi'与pi''，如果在p中存在一条pi到pj的边，那么在二分图Ｐ＇中就有一条连接pi'与pj''的无向边；这里pi' 就是p中pi的出边，pj''就是p中pj 的一条入边；

对于公式：最小路径覆盖＝｜Ｐ｜－最大匹配数；可以这么来理解；

如果匹配数为零，那么Ｐ中不存在有向边，于是显然有：

最小路径覆盖＝｜Ｐ｜－最大匹配数＝｜Ｐ｜－０＝｜Ｐ｜；即Ｐ的最小路径覆盖数为｜Ｐ｜；

Ｐ＇中不在于匹配边时，路径覆盖数为｜Ｐ｜；

如果在Ｐ＇中增加一条匹配边pi'－－＞pj''，那么在图P的路径覆盖中就存在一条由pi连接pj的边，也就是说pi与pj 在一条路径上，于是路径覆盖数就可以减少一个；

如此继续增加匹配边，每增加一条，路径覆盖数就减少一条；直到匹配边不能继续增加时，路径覆盖数也不能再减少了，此时就有了前面的公式；但是这里只是说话了每条匹配边对应于路径覆盖中的一条路径上的一条连接两个点之间的有向边；下面来说明一个路径覆盖中的每条连接两个顶点之间的有向边对应于一条匹配边；

与前面类似，对于路径覆盖中的每条连接两个顶点之间的每条有向边pi--->pj，我们可以在匹配图中对应做一条连接pi'与pj''的边，显然这样做出来图的是一个匹配图（这一点用反证法很容易证明，如果得到的图不是一个匹配图，那么这个图中必定存在这样两条边 pi'---pj'' 及 pi' ----pk''，（j!=k），那么在路径覆盖图中就存在了两条边pi-->pj, pi--->pk ，那边从pi出发的路径就不止一条了，这与路径覆盖图是矛盾的；还有另外一种情况就是存在pi'---pj'',pk'---pj''，这种情况也类似可证）；

至此，就说明了匹配边与路径覆盖图中连接两顶点之间边的一一对应关系，那么也就说明了前面的公式成立！

1 #include <iostream>
2 using namespace std;
3 int n,m;
4 int map[250][250];
5 bool visit[500];
6 int l[500];//邻接点
7 bool find(int a)
8 {
9       for(int i=1;i<=n;++i)
10             if(map[2*a][2*i-1]&&!visit[2*i-1])
11             {
12                   visit[2*i-1]=1;
13                   if(!l[2*i-1]||find(l[2*i-1]))
14                   {
15                         l[2*i-1]=a;
16                         return true;
17                   }
18             }
19       return false;
20 }
21 int main()
22 {
23       int cas,a,b;
24       scanf("%d",&cas);
25       for(int i=1;i<=cas;++i)
26       {
27             memset(l,0,sizeof(l));
28             memset(map,0,sizeof(map));
29             scanf("%d%d",&n,&m);
30             //把节点分成两个节点，2*i是出节点,2*i-1是如节点
31             for(int j=1;j<=m;++j)
32             {
33                   scanf("%d%d",&a,&b);
34                   map[2*a][2*b-1]=1;
35             }
36             int ans=0;
37             for(int i=1;i<=n;++i)
38             {
39                   memset(visit,0,sizeof(visit));
40                   if(find(i))ans++;
41             }
42             printf("%d\n",n-ans);
43       }
44       return 0;
45 }

SHFACM 2009-02-05 14:36 发表评论

差分约束系统（zoj1508）

SHFACM — Thu, 05 Feb 2009 03:32:00 GMT

给出一组限制条件 a[i] - a[j] ≥ k 或 a[i] - a[j] ≤ k。
要你求出a[t] - a[s]的最小值或最大值。

先举一个题目的例子：poj1201.
题目大意是，有一个集合S。已知其满足以下一些条件：
对于给出的n组 a[i] b[i] c[i]，有从a[i]~b[i]这连续的k个整数中，至少有c[i]个在集合S内。求S最少的元素个数。

这个题目转化为我们的差分约束系统如下：
如果i∈S，则t[i]=1，否则t[i]=0。另s[i] = ∑t[j] (j = 0 ~ i)，这样子，题目的条件就可以用下面的式子表示：
s[b[i]] - s[a[i]-1] ≥ c[i]
s[i] - s[i+1] ≥ -1
s[i+1] - s[i] ≥ 0
注意后面两个式子是s先天的性质。
我们要求的就是s[n] - s[-1]的最小值（因为题目都是非负的嘛）。

然后我们介绍解决差分约束问题的方法：Bellman-Ford算法，是不是很神奇呢？没错，差分约束系统可以通过转换成图论最短路问题来解决：
注意到最短路算法的松弛操作：if (d[j] > d[i] + w[i][j]) d[j] = d[i] + w[i][j]。
这其中的三角形不等式：d[j] ≤ d[i] + w[i][j]简单变形就成了d[i] - d[j] >= -w[i][j]。这样就图形的最短路就维护了一个不等式组。所以，我们可以建立一个图：对于每一个不等式s[i] - s[j] >= c，就从j连一条指向i的边，其中边的权值c，这样求一个最长路，就是d[n] - d[-1]就是s[n] - s[-1]的最小值了，且对应的方案就是s[i] = d[i]。

有的同学要问了：无解怎么办啊？很简单，你将会发现Bellman-Ford算法如果找出了”负权回路”，那么该系统无解。只要系统无解，就必然存在”负权圈”。
那么如果求s[n] - s[-1]的最小值呢？其实和上面的方法类似了，大家可以自己推导一下。而且有很多问题仅仅要你给出是否有解的判断，那就不要想那么多了。

实际上是求最长路，其实就是把松弛操作的符号改变即可

其实此题可以用spfa实现，效率很高

开始做此题时

连续超时很久

此题每次要进行三次松弛操作

1 for(int j=Min;j<Max;++j)
2 {
3       if(d[j]!=INT_MIN&&d[j]>d[j+1])
4       {
5             d[j+1]=d[j];
6             update=0;
7       }
8 }
9 for(int j=Max;j>Min;--j)
10 {
11       if(d[j]!=INT_MIN&&d[j]-1>d[j-1])
12       {
13             update=0;
14             d[j-1]=d[j]-1;
15       }
16 }

一开始将两个松弛操作合并到一起进行

超时

第二次分开

仍然超时

第三次

改变松弛的顺序

即第三个松弛从上到下（之前是从下到上）

这样做的目的就是避免了重复的松弛操作！

1 #include <iostream>
2 using namespace std;
3 struct Edge
4 {
5       int x,y,d;
6 }edge[50000+5];
7 int n;
8 int d[50000+5];
9 int main()
10 {
11      while(scanf("%d",&n)!=EOF)
12      {
13             int Min=INT_MAX;
14             int Max=INT_MIN;
15             for(int i=0;i<n;++i)
16             {
17                   scanf("%d%d%d",&edge[i].x,&edge[i].y,&edge[i].d);
18                   if(--edge[i].x<Min)Min=edge[i].x;
19                   if(edge[i].y>Max)Max=edge[i].y;
20             }
21             int tmp=Max-Min+1;
22             for(int i=Min;i<=Max;++i)
23                   d[i]=INT_MIN;
24             d[Min]=0;
25             for(int i=0;i<tmp;++i)
26             {
27                   bool update=1;
28                   for(int j=0;j<n;++j)
29                   {
30                         if(d[edge[j].x]!=INT_MIN&&d[edge[j].y]<d[edge[j].x]+edge[j].d)
31                         {
32                               update=0;
33                               d[edge[j].y]=d[edge[j].x]+edge[j].d;
34                         }
35                   }
36                   for(int j=Min;j<Max;++j)
37                   {
38                         if(d[j]!=INT_MIN&&d[j]>d[j+1])
39                         {
40                               d[j+1]=d[j];
41                               update=0;
42                         }
43                     }
44                   for(int j=Max;j>Min;--j)
45                   {
46                         if(d[j]!=INT_MIN&&d[j]-1>d[j-1])
47                         {
48                               update=0;
49                               d[j-1]=d[j]-1;
50                         }
51                   }
52                   if(update)break;
53             }
54             printf("%d\n",d[Max]-d[Min]);
55       }
56       return 0;
57 }

SHFACM 2009-02-05 11:32 发表评论

memset用法（转）

SHFACM — Wed, 04 Feb 2009 10:18:00 GMT

memset的正规用法是只能用来初始化char类型的数组的，也就是说，它只接受0x00-0xFF的赋值
然而，在大多数情况下，需要对一个double或int的数组赋一个相对很大或很小的初值

以下的赋值方式是不正确的：

memset(arr,2147483647,sizeof(arr));

但是可以用一些技巧，来得到一个差不多的最大值，比如像：

memset(arr,0x7F,sizeof(arr));

它将arr中的值全部赋为2139062143
这是用memset对int赋值所能达到的最大值

类似的还有：

memset(arr,0x80,sizeof(arr)); //set int to -2139062144
memset(arr,0x7F,sizeof(arr)); //set double to 1.38242e+306
memset(arr,0xFE,sizeof(arr)); //set double to -5.31401e+303

SHFACM 2009-02-04 18:18 发表评论

zoj 1082(floyd)

SHFACM — Wed, 04 Feb 2009 10:17:00 GMT

1 #include<iostream>
2 using namespace std;
3 int n,m;
4 int d[101][101];
5 int main()
6 {
7       int a,b;
8       while(scanf("%d",&n)&&n)
9       {
10             //用memset无法赋值INT_MAX
11             for (int i=1;i<=n;++i)
12                   for(int j=1;j<=n;++j)
13                         d[i][j]=INT_MAX;
14             for(int i=1;i<=n;++i)
15             {
16                   scanf("%d",&m);
17                   for(int j=1;j<=m;++j)
18                   {
19                         scanf("%d%d",&a,&b);
20                         d[i][a]=b;
21                   }
22             }
23             for(int k=1;k<=n;++k)
24                   for(int i=1;i<=n;++i)
25                         for(int j=1;j<=n;++j)
26                               if(d[i][k]<INT_MAX&&d[k][j]<INT_MAX&&d[i][j]>d[i][k]+d[k][j])
27                                     d[i][j]=d[i][k]+d[k][j];
28             int Max;
29             int Min=INT_MAX;
30             int point=-1;
31             bool connect;
32             for(int i=1;i<=n;++i)
33             {
34                   connect=1;
35                   Max=-1;
36                   for(int j=1;j<=n;++j)
37                         if(i!=j)
38                         {
39                               if(d[i][j]==INT_MAX)
40                               {
41                                     connect=0;
42                                     break;
43                               }
44                               Max=max(Max,d[i][j]);
45                         }
46                   if(connect&&Max<Min)
47                   {
48                         Min=Max;
49                         point=i;
50                   }
51             }
52             if(point==-1)printf("disjoint\n");
53             else printf("%d %d\n",point,Min);
54       }
55       return 0;
56 }

SHFACM 2009-02-04 18:17 发表评论

zoj 2833

SHFACM — Wed, 04 Feb 2009 05:55:00 GMT

1 //并查集
2 //并查集可以判断图的连通性
3 //并查集其实还有一个优化：就是路径压缩:即找到u所在树的跟v以后，把从u到v的路径上的所有点的父亲都设置为v,这样可以有效的减少查找的时间
4 //zoj2833
5 #include <iostream>
6 using namespace std;
7 int n,m;
8 int father[100000+1];
9 int f[100000+1];//朋友的个数
10 int rank[100000+1];
11 void make_set(int s)
12 {
13       for(int i=1;i<=s;++i)
14       {
15             f[i]=1;
16             father[i]=i;
17             rank[i]=0;
18       }
19 }
20 int find_set(int x)
21 {
22       if(x!=father[x])
23             father[x]=find_set(father[x]);
24       return father[x];
25 }
26 void union_set(int x,int y)
27 {
28       int a=find_set(x);
29       int b=find_set(y);
30       if(rank[a]>rank[b])
31       {
32             father[b]=a;
33             f[a]+=f[b];
34       }
35       else
36       {
37             father[a]=b;
38             f[b]+=f[a];
39       }
40       if(rank[a]==rank[b])rank[b]++;
41 }
42
43 int main()
44 {
45       int a,b;
46       char tmp;
47       int cas=0;
48       while(scanf("%d%d",&n,&m)!=EOF)
49       {
50             if(cas)printf("\n");
51             printf("Case %d:\n",++cas);
52             make_set(n);
53             getchar();
54             for(int i=1;i<=m;++i)
55             {
56                   tmp=getchar();
57                   if(tmp=='M')
58                   {
59                         scanf("%d%d",&a,&b);
60                         if(find_set(a)!=find_set(b))
61                               union_set(a,b);
62                   }
63                   if(tmp=='Q')
64                   {
65                         scanf("%d",&a);
66                         int sum=f[find_set(a)];
67                         printf("%d\n",sum);
68                   }
69                   getchar();
70             }
71       }
72       return 0;
73 }
74

SHFACM 2009-02-04 13:55 发表评论