題意是中文的,就不說了;
這裡用到種類並查集,分別用1-N;N-2N,2N-3N代表城市,服務,人;
然後要注意這幾點:
1:不要用rank數組了,因為連邊要自己控制。
2:在unite函數的時候,比較一下x和y,控制把大的連到小的上面,這樣之後尋味的時候,find()一定會找到最小的(城市),然後如果大於N,就說明他沒有連到城市,輸出0;
代碼如下:
#include#include #include #include #include #include using namespace std; const int N = 300000; int par[999999], last[999999]; void init(int n) { int i, j; for (int i = 0; i N) { printf("0\n"); continue; } printf("%d\n", temp); } } return 0; }