LA 3644易爆物

【题目描述】:有一些简单化合物，每种化合物由两种元素组成。但是，当车上存在k中化合物，而且存在k种元素，就会爆炸。现在依次向车上装载，装载序列由输入给出，当会某物品装载后爆炸时，就不会装载这个，最终统计有多少个物品没有被装载上。

【算法分析】:

首先这个问题不是线性描述的，而是解决多个变量之间的冲突问题。这时候，我们是不是就要想到用图论来解决了？首先看题目中给出的例子，如果AB、BC、CD、AD，放进去就会爆炸，而AB，BC，AD，放进去就不会爆炸，而这道题使容易引起歧义的。但后面的例子解决了这个问题。必须k种元素都参与到爆炸行为中来。那么，就像第一个例子，k种元素，没中元素出现的次数为2，联想到节点的度数，即k个节点，每个节点的度为2，那么满足这个模型的就是形成了一个环。那么判环用并查集解决就比较方便了。

【完整代码】：

 1 #include<iostream>
 2 
 3 #include<stdio.h>
 4 
 5 #include<string.h>
 6 
 7 #include<algorithm>
 8 
 9 #include<stdlib.h>
10 
11 #include<math.h>
12 
13 #include<queue>
14 
15 #include<vector>
16 
17 #include<map>
18 
19 #define MAXN 100000+10
20 
21 #define MAXM 20000+5
22 
23 #define oo 9556531
24 
25 #define eps 0.000001
26 
27 #define PI acos(-1.0)
28 
29 #define REP1(i,n) for(int i=0;i<(n);i++)
30 
31 #define REP2(i,n) for(int i=1;i<=(n);i++)
32 
33 using namespace std;
34 
35  
36 
37 int p[MAXN],ans;
38 
39 int find(int x)
40 
41 {
42 
43     return x==p[x]?x:p[x]=find(p[x]);
44 
45 }
46 
47 void merge(int x,int y)
48 
49 {
50 
51     int px=find(x),py=find(y);
52 
53     if (px!=py) p[px]=py;
54 
55     return;
56 
57 }
58 
59 void init()
60 
61 {
62 
63     ans=0;
64 
65     for(int i=1;i<MAXN;i++) p[i]=i;
66 
67 }
68 
69 int main()
70 
71 {
72 
73     int x,y;
74 
75     init();
76 
77     while(cin>>x)
78 
79     {
80 
81         if(x==-1) {cout<<ans<<endl;init();continue;}
82 
83         cin>>y;
84 
85         if (find(x)==find(y)) {ans++;continue;}
86 
87         merge(x,y);
88 
89     }
90 
91     return 0;
92 
93 }
94 
95

【关键词】：图论建模，读题