亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

hdu 1811 Rank of Tetris

系統 1656 0

Time Limit: 1000/1000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1109????Accepted Submission(s): 275

?????? 本題對本人來說絕對是一個挑戰,因為以前我從來沒有寫過拓撲排序也沒用過set,這是我第一次的嘗試,雖然wrong了很多次花費了一整天的時間,但還是應當值得紀念的。本題的思想就是拓撲排序+并查集。

???? 注意事項:

??? (1)因為本題數據比較大,用鄰接矩陣存儲太浪費空間了,我就因此而超內存好幾次,建議使用鄰接表。特別是對這種稀疏矩陣,采用鄰接表即可節約空間又可節約時間

???? (2)一定要找完才能判斷,如果同時又CONFLICT和UNCERTAIN輸出CONFLICT

???? (3)使用并查集一定要小心,如果對某個節點操作一定要轉化為對根節點的操作,因為本題的思想就是用并查集把相同放到一個集合看成是一個節點。

? 代碼:

??

?

      
1 #include < iostream >
2 #include < set >
3 ? using namespace std;
4 typedef struct t
5 {
6 int data;
7 struct t * next;
8 }T;
9 ? struct node
10 {
11 int in ;
12 int root;
13 struct t * next;
14 bool operator < ( const node & a) const
15 {
16 if (a. in == in )
17 return a.root > root;
18 else return a. in > in ;
19 }
20 }s[ 10005 ];
21 ? int father[ 10005 ],rank[ 10005 ],a1[ 10005 ],c1[ 10005 ]; char d[ 10005 ];
22 ? void insert( int a, int c)
23 {
24 node * t =& s[a];
25 T * x = (T * )malloc( sizeof (T));
26 s[c]. in ++ ;
27 x -> data = c;
28 x -> next = t -> next;
29 t -> next = x;
30 }
31 int find( int x)
32 {
33 if (x != father[x])
34 father[x] = find(father[x]);
35 return father[x];
36 }
37 void Union( int x, int y)
38 {
39 x = find(x);
40 y = find(y);
41 if (x == y)
42 return ;
43 if (rank[x] > rank[y])
44 {
45 father[y] = x;
46 }
47 else
48 {
49 if (rank[x] == rank[y])
50 rank[y] ++ ;
51 father[x] = y;
52 }
53 }
54 int main()
55 {
56 set < node > se;
57 node cur1,cur2;
58 int n,m,i,a,c,k,j,mark1,mark2; char b;
59 while (scanf( " %d%d " , & n, & m) != EOF)
60 {
61 j = 0 ;
62 se.clear ();
63 for (i = 0 ;i < n;i ++ )
64 {
65 father[i] = i;
66 s[i]. in = 0 ;
67 s[i].next = NULL;
68 s[i].root = i;
69 rank[i] = 0 ;
70 }
71 for (i = 1 ;i <= m;i ++ )
72 {
73 scanf( " %d " , & a);
74 getchar();
75 scanf( " %c " , & b);
76 scanf( " %d " , & c);
77 if (b == ' = ' )
78 Union(a,c);
79 else
80 {
81 j ++ ;
82 d[j] = b;
83 a1[j] = a;
84 c1[j] = c;
85 }
86 }
87 for (k = 1 ;k <= j;k ++ )
88 if (d[k] == ' > ' )
89 {
90 a = find(a1[k]);c = find(c1[k]);insert(a,c);
91 }
92 else
93 {
94 a = find(a1[k]);c = find(c1[k]);insert(c,a);
95 }
96
97 for (i = 0 ;i < n;i ++ )
98 se.insert (s[find(i)]);
99 mark1 = 0 ;mark2 = 0 ;
100 set < node > ::iterator it1;
101 set < node > ::iterator it2;
102 while ( ! se.empty ())
103 {
104 it1 = se.begin();
105 if (( * it1). in != 0 )
106 {
107 mark1 = 1 ;
108 cout << " CONFLICT " << endl;
109 break ;
110 }
111 T * t;
112 t = ( * it1).next;
113 se.erase(se.begin ());
114 if (se.empty ())
115 break ;
116 it2 = se.begin ();
117 if (( * it2). in == 0 )
118 {
119 mark2 = 1 ;
120 }
121 while (t != NULL)
122 {
123 se.erase (s[t -> data]);
124 s[t -> data]. in -- ;
125 se.insert(s[t -> data]);
126 t = t -> next;
127 }
128 }
129 if (mark1 == 0 )
130 if (mark2 == 1 )
131 cout << " UNCERTAIN " << endl;
132 else
133 cout << " OK " << endl;
134 }
135 return 0 ;
136 }
137
138
139
140
141
142

?

?

hdu 1811 Rank of Tetris


更多文章、技術交流、商務合作、聯系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯系: 360901061

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 六色视频| 操熟美女又肥又嫩的骚屁股 | 四虎精品永久在线 | 干干操操| 老子午夜影院 | 欧美视频在线一区二区三区 | 天天操天天摸天天干 | 亚洲成a人片77777kkk | 91久久国产成人免费观看资源 | 亚洲视屏在线观看 | 日本不卡中文字幕一区二区 | 久久精品美女 | 亚洲精品色婷婷在线影院麻豆 | 欧美成人h版影片在线观看 欧美成人h精品网站 | 精品成人一区二区 | 99热这里只有精品第一页 | 一本一本久久a久久精品综合 | 亚洲欧美卡通成人制服动漫 | 久久精品影院永久网址 | 国产成人久久蜜一区二区 | 欧美色成人tv在线播放 | 欧美精欧美乱码一二三四区 | 色婷婷天天综合在线 | 久草色播 | 国产永久| 欧洲一区在线观看 | 高清不卡日本v在线二区 | 久久天天躁狠狠躁狠狠躁 | 亚洲欧美综合另类 | 久久精品国产线看观看亚洲 | 欧美又粗又硬又大久久久 | 毛片免费观看久久欧美 | 亚洲一级理论片 | 播五月综合 | 亚州色拍拍拍 | ww亚洲ww亚在线观看 | 国产在线99| 奇米奇米色 | 国产精品久久久久久久久久免费 | 亚洲 欧美 日韩 综合 | 男人私人影院免费看视频 |