Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

Korea has many tourist attractions. One of them is an archipelago (Dadohae in Korean), a cluster of small islands scattered in the southern and western coasts of Korea. The Korea Tourism Organization (KTO) plans to promote a new tour program on these islands. For this, The KTO wants to designate two or more islands of the archipelago as a tour belt.

There are n islands in the archipelago. The KTO focuses on the synergy effect created when some islands are selected for a tour belt. Synergy effects are assigned to several pairs of islands. A synergy effect SE(u, v) or SE(v, u) between two islands u and v is a positive integer which represents a value anticipated when both u and v are included in a tour belt. The KTO wants to select two or more islands for the tour belt so that the economic benefit of the tour belt is as high as possible.

To be precise, we define a connected graph G = (V, E), where V is a set of n vertices and E is a set of m edges. Each vertex of V represents an island in the archipelago, and an edge (u, v) of E exists if a synergy effect SE(u, v) is defined between two distinct vertices (islands) u and v of V. Let A be a subset consisting of at least two vertices in V. An edge (u, v) is an inside edge of A if both u and v are in A. An edge (u, v) is a border edge of A if one of u and v is in A and the other is not in A.

A vertex set B of a connected subgraph of G with 2| B|n is called a candidate for the tour belt if the synergy effect of every inside edge of B is larger than the synergy effect of any border edge of B. A candiate will be chosen as the final tour belt by the KTO. There can be many possible candidates in G. Note that V itself is a candidate because there are no border edges. The graph in Figure 1(a) has three candidates {1,2}, {3,4} and {1,2,3,4}, but {2,3,4} is not a candidate because there are inside edges whose synergy effects are not larger than those of some border edges. The graph in Figure 1(b) contains six candidates, {1,2}, {3,4}, {5,6}, {7,8}, {3,4,5,6} and {1,2,3,4,5,6,7,8}. But {1,2,7,8} is not a candidate because it does not form a connected subgraph of G, i.e., there are no edges connecting {1,2} and {7,8}.

The KTO will decide one candidate in G as the final tour belt. For this, the KTO asks you to find all candidates in G. You write a program to print the sum of the sizes of all candidates in a given graph G. For example, the graph in Figure 1(a) contains three candidates and the sum of their sizes is 2 + 2 + 4 = 8, and the graph in Figure 1(b) contains six candidates and the sum of their sizes is 2 + 2 + 2 + 2 + 4 + 8 = 20.

Input 

Your program is to read input from standard input. The input consists of T test cases. The number of test cases T is given in the first line of the input. Each test case starts with a line containing two integers n ( 2n5, 000) and m ( 1m), where n represents the number of vertices (islands) and m represents the number of edges of a connected graph G. Islands are numbered from 1 to n. In the following m lines, the synergy effects assigned to m edges are given; each line contains three integers, u, v, and k ( 1uvn, 1k10⁵), where k is the synergy effect between two distinct islands u and v, i.e., SE(u, v) = SE(u, v) = k.

Output 

Your program is to write to standard output. Print exactly one line for each test case. Print the sum of the sizes of all candidates for a test case.

The following shows sample input and output for two test cases.

Sample Input 

2
4 6
1 2 3
2 3 2
4 3 4
1 4 1
2 4 2
1 3 2
8 7
1 2 2
2 3 1
3 4 4
4 5 3
5 6 4
6 7 1
7 8 2

Sample Output 

8
20

---

題目描述：

將圖形中的點畫分成兩個 s-t 集合，而 s-t 中的邊必須全小於 s 自己本身內部相連的邊。

問所有 s 的所有可能，計算其 size 總和即可。

題目解法：

不可能窮舉所有 s 的情況去進行檢查，因此考慮最小生成樹的思路。

而這裡相反，將權重大的先放入，根據 Kruskal 的想法逐一放入。

每放一次就進行檢查，之所以這麼做是為了要保證集合內部的權重的最小值盡可能地大於連外的所有權重，

那麼最大的那個點會被放進來，但他所造成影響可能會那條邊更小，對於其他相同情況的點不會影響。

因為題目要求的是 <, 而不是 <=，所以是可以允許的，在邏輯上不會有錯誤。

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
struct E {
    int x, y, v;
    bool operator<(const E &a) const {
        return v > a.v;
    }
};
E D[1250000];
vector<int> g[5005];
int p[5005], rank[5005];//disjoint set.
int findp(int x) {
    return p[x] == x ? x : (p[x]=findp(p[x]));
}
int joint(int x, int y) {
    x = findp(x), y = findp(y);
    if(x == y)  return 0;
    if(rank[x] > rank[y])
        rank[x] += rank[y], p[y] = x;
    else
        rank[y] += rank[x], p[x] = y;
    return 1;
}
int check(int x, int n) {//divide s-t set
    int smn = 0xfffff, tmx = 0;
    int i, j, y, pp, e;
    E edge;
    x = findp(x);
    for(i = 1; i <= n; i++) {
        pp = findp(i);
        if(pp != x) continue;
        // find a set {s}
        for(j = 0; j < g[i].size(); j++) {
            e = g[i][j];
            edge = D[e];
            if(edge.x != i)
                pp = findp(edge.x);
            else
                pp = findp(edge.y);
            if(pp == x) //same {s}
                smn = min(smn, edge.v);
            else
                tmx = max(tmx, edge.v);
        }
        if(smn < tmx)   return false;
    }
    return smn > tmx;
}
void MST(int n, int m) {//max spanning tree
    int ret = 0, i, j;
    for(i = 1; i <= n; i++)
        p[i] = i, rank[i] = 1;
    sort(D, D+m);
    for(i = 0; i < m; i++) {
        g[D[i].x].push_back(i);
        g[D[i].y].push_back(i);
    }
    for(i = 0; i < m; i++) {
        if(joint(D[i].x, D[i].y)) {
            if(check(D[i].x, n))
                ret += rank[findp(D[i].x)];
        }
    }
    printf("%d\n", ret);
}
int main() {
    int testcase, n, m, i;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d %d", &n, &m);
        for(i = 1; i <= n; i++)
            g[i].clear();
        for(i = 0; i < m; i++)
            scanf("%d %d %d", &D[i].x, &D[i].y, &D[i].v);
        MST(n, m);
    }
    return 0;
}