[ZJ][拓樸] d917. 5. 貼磁磚
內容 ：
李先生擁有一棟別墅，由於浴室的地板磁磚已經老舊，因此他想要自己動手重新貼上漂亮的磁磚。他開著車子去買正方形磁磚，當他挑選好想要的磁磚後卻不知道如何擺置才好看，於是老闆就配色上的美觀給了他一些建議，他回到家後，就老闆的建議開始對磁磚擺置做規劃。
假設李先生挑選了 n 個長、寬皆為 w 的正方形磁磚，每個磁磚顏色都不同，並將磁磚編號為 1, 2, …, n。老闆的建議是每個磁磚必須沿著水平線與垂直線擺放 (即不能旋轉)，同時任二個磁磚的位置必存在一種相對關係 (即上下或左右關係)。假設 i(1 ≤ i ≤ n)、j(1 ≤ j ≤ n , i ≠ j) 為任兩片磁磚的編號，(xi, yi)、(xj, yj) 分別表示 i、j 這兩片磁磚擺放後的左下角座標，(xi+w, yi+w)、(xj+w, yj+w) 分別表示它們擺放後的右上角座標。當老闆建議將 i 放在 j 的右邊時，則於完成磁磚擺放後，必須滿足 xj+w ≤ xi；當老闆建議將 i 放在 j 的上面時，則於完成磁磚擺放後，必須滿足 yj+w ≤ yi。此外，相對位置的關係具有可傳遞性，例如：磁磚 i 被建議放在磁磚 j 的上面，磁磚 j 被建議放在磁磚 k 的上面，則磁磚 i 一定被建議放在磁磚 k 的上面；但是不會出現矛盾情形，例如：磁磚 i 被建議放在磁磚 j 的上面，且磁磚 j 被建議放在磁磚 k 的上面，則不會出現將磁磚 k 放在磁磚 i 上面的建議。此外，為了節省浴室空間，李先生希望能將這些磁磚擺置於一個矩形 (含正方形) 區域內，而且該區域的面積要越小越好。
為了節省時間，李先生希望你能幫忙寫一個程式，規劃出一個符合老闆建議 (即每個磁磚必須沿著水平線與垂直線擺放，並滿足 n(n-1)/2 種磁磚相對位置關係) 的磁磚擺置方式，而且包圍這個磁磚擺置方式的矩形面積必須是所有滿足老闆建議的擺置方式中的最小值。你的程式必須算出該最小面積，回報給李先生。
以下為一範例：假設李先生購買了 4 個長、寬皆為 1 的正方形磁磚，並將磁磚編號為 1~4，按照老闆的建議，這些磁磚的相對位置關係如下：2 要擺在 4 的右邊、1 要擺在 4 的上面、1 要擺在 2 的上面、3 要擺在 1 的上面、3 要擺在 4 的上面、和 3 要擺在 2 的上面。下圖列出四種滿足老闆建議的擺置方式，其中後二種方式 ((c) 與 (d)) 可分別用面積為 9 的矩形區域將其圍住，而前二種方式 ((a) 與 (b)) 則分別只需用面積為 6 的矩形區域將其圍住。就本範例而言，所有滿足老闆建議的擺置方式中最小的矩形面積為 6 ，所以你的程式必須回報 6 給李先生。
輸入說明
：
輸出說明
：
範例輸入
：
輸入範例 1: 4 1 2 4 0 1 4 1 1 2 1 3 1 1 3 4 1 3 2 1 輸入範例 2: 6 3 2 1 0 3 2 0 3 1 0 6 4 0 4 1 1 5 1 1 4 2 1 5 2 1 4 3 1 5 3 1 5 4 1 6 1 1 6 2 1 6 3 1 5 6 1
範例輸出 ：
輸出範例 1: 6 輸出範例 2: 81
提示
：
出處
：
由於給定所有的關係, 而且不會重複, 那麼肯定是一個固定格式,
只要求出兩張圖的拓樸深度即可
#include <stdio.h>
#include <vector>
using namespace std;
int main() {
int n, w, a, b, c, i;
while(scanf("%d %d", &n, &w) == 2) {
int m = n*(n-1)/2;
vector<int> g1[501], g2[501], b1[501], b2[501];
int indeg1[501] = {}, indeg2[501] = {};
while(m--) {
scanf("%d %d %d", &a, &b, &c);
if(c == 0) {
g1[b].push_back(a);/*b->a*/
b1[a].push_back(b);
indeg1[a]++;
} else {
g2[a].push_back(b);/*a->b*/
b2[b].push_back(a);
indeg2[b]++;
}
}
int flag = 1, used1[501] = {}, ac1[501] = {};
do {
flag = 0;
for(i = 1; i <= n; i++) {
if(indeg1[i] <= 0 && used1[i] == 0) {
used1[i] = 1;
for(vector<int>::iterator it = b1[i].begin();
it != b1[i].end(); it++) {
ac1[i] = ac1[i] > ac1[*it] ? ac1[i] : ac1[*it];
}
ac1[i]++;
for(vector<int>::iterator it = g1[i].begin();
it != g1[i].end(); it++) {
indeg1[*it]--;
}
flag = 1;
}
}
} while(flag);
int used2[501] = {}, ac2[501] = {};
do {
flag = 0;
for(i = 1; i <= n; i++) {
if(indeg2[i] <= 0 && used2[i] == 0) {
used2[i] = 1;
for(vector<int>::iterator it = b2[i].begin();
it != b2[i].end(); it++) {
ac2[i] = ac2[i] > ac2[*it] ? ac2[i] : ac2[*it];
}
ac2[i]++;
for(vector<int>::iterator it = g2[i].begin();
it != g2[i].end(); it++) {
indeg2[*it]--;
}
flag = 1;
}
}
} while(flag);
int R = 0, L = 0;
for(i = 1; i <= n; i++) {
R = R > ac1[i] ? R : ac1[i];
L = L > ac2[i] ? L : ac2[i];
}
printf("%d\n", R*L*w*w);
}
return 0;
}