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

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在线v网站 | 久久人人干| 午夜性爽视频男人的天堂在线 | 国产毛片久久国产 | 亚洲一区二区免费在线观看 | 伊人成人久久 | 曰本一区 | 丁香午夜| 欧美操人视频 | 亚洲视频一区在线播放 | 久久综合桃花网 | 国产精品人伦久久 | 九九资源站 | 国产日韩欧美91 | 曰批免费视频播放在线看片 | 久久国产精品自由自在 | h片免费观看 | 免费观看a毛片一区二区不卡 | 日夜操在线视频 | 毛片网站免费在线观看 | 四虎在线精品 | 日本一级做人免费视频 | 国产精品久久久久亚洲 | 亚洲成a v人片在线观看 | 国产一区二区精品久久小说 | 九九热视频免费在线观看 | 黄毛片免费 | 亚洲黄色在线视频 | 国产欧美精品一区aⅴ影院 国产欧美精品一区二区 | 伊人久久免费视频 | 久久香蕉国产线看精品 | 日本一级在线观看视频播放 | 国产成人aa视频在线观看 | 全黄大全大色全免费大片 | 免费一级黄色毛片 | 亚洲欧美视频二区 | 久久精品国产精品亚洲精品 |