PAT (Top Level) Practise 1013 Image Segmentation (35)

Image segmentation is usually formulated as a graph partition problem, where each segment corresponds to a connected component. Moreover, each pixel is the vertex of the graph. Each edge has a weight, which is a non-negative dissimilarity between neighboring pixels. So, the goal of image segmentation is to decompose the image graph into several disconnected components, where the elements in a component are similar and the elements in the different components are dissimilar.

The components are defined as follows:

• A component is made of a set of connected vertices;
• Any two components have no shared vertices;
• The dissimilarity D(C1, C2) of any two components C1 and C2 is larger than the confidence H of any of C1 and C2.
• The dissimilarity D(C1, C2) is defined to be the minimum edge weight of all the edges connecting C1 and C2, or infinity if no such edge exists;
• The confidence of a component C, H(C), is defined to be the maximum edge weight of the minimum spanning tree of C, plus a function f(C) = c/|C| where c is a positive constant and |C| is the size of the component C;
• A set of vertices must not be treated as a component if they can be partitioned into two or more components.

Your job is to write a program to list all the components.

Input Specification:

Each input file contains one test case. For each case, the first line contains three integers: Nv (0 < Nv <=1000), the total number of vertices (and hence the vertices are numbered from 0 to Nv-1); Ne, the total number of edges; and c, the constant in the function f(C). Then Ne lines follow, each gives an edge in the format:

V1 V2 Weight

Note: it is guaranteed that each pixel has no more than 8 neighboring pixels. The constant and all the weights are positive and are no more than 1000.

Output Specification:

For each case, list each component in a line. The vertices in a component must be printed in increasing order, separated by one space with no extra space at the beginning or the end of the line. The components must be listed in increasing order of their first vertex.

Sample Input 1:

10 21 100
0 1 10
0 3 60
0 4 90
1 2 90
1 3 50
1 4 200
1 5 86
2 4 95
2 5 5
3 4 95
3 6 15
3 7 101
4 5 500
4 6 100
4 7 101
4 8 101
5 7 300
5 8 50
6 7 90
7 8 84
7 9 34      

Sample Output 1:

0 1 3 6
2 5 8
4
7 9      

Sample Input 2:

7 7 100
0 1 10
1 2 61
2 3 50
3 4 200
4 5 82
5 0 200
3 6 90      

Sample Output 2:

0 1
2 3 6
4 5      

題面有點惡心，對于我這種英語水準弱渣到不行的人來說簡直就是讀題比寫題難啊。拖了好久的題了，之前一直不是很了解樣例二怎麼來的，現在拿起來猜了猜，竟然猜對了。

簡單解釋一下題意吧，給你一個圖，和一些有邊權的邊，要你分塊，每個分塊自身有一個H=最小生成樹的最大邊+常數C/塊内的點數，

要求，任意兩個分塊之間最小的連接配接邊的長度要大于一個分塊的H（随便哪個都行，這個地方了解看題目any of）,

我的做法就是，把所有邊按權值排序，一條一條加入，判斷是否需要這條邊，不用就不加。然後就分完塊了，排個序輸出就好了。

正确性的話，想想應該是對的，證明就略了吧。

#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define loop(i,j,k) for (int i=j;i!=-1;i=k[i])
#define inone(x) scanf("%d",&x)
#define intwo(x,y) scanf("%d%d",&x,&y)
#define inthr(x,y,z) scanf("%d%d%lf",&x,&y,&z)
const int N = 1e5+ 10;
const double INF = 1e18;
int n, m;
int fa[N], c[N];
double s[N], C;
vector<int> p[N];

struct point
{
  int x, y;
  double z;
  bool operator<(const point&a)const { return z < a.z; }
}a[N];

int get(int x) 
{ 
  if (x == fa[x]) return x;
  fa[x] = get(fa[x]);
  c[fa[x]] += c[x]; c[x] = 0;
  return fa[x];
}

bool cmp(vector<int> a,vector<int> b)
{
  if (!a.size() && b.size()) return true;
  if (b.size() == 0) return false;
  return a[0] < b[0];
}

int main()
{
  while (inthr(n, m, C) != EOF)
  {
    rep(i, 0, n - 1) s[i] = 0, c[i] = 1, fa[i] = i;
    rep(i, 0, n - 1) p[i].clear();
    rep(i, 1, m) inthr(a[i].x, a[i].y, a[i].z);
    sort(a + 1, a + m + 1);
    rep(i, 1, m)
    {
      int fx = get(a[i].x), fy = get(a[i].y);
      if (fx == fy) continue;
      if (fx < fy) swap(fx, fy);
      if (s[fx] + C / c[fx] < a[i].z) continue;
      if (s[fy] + C / c[fy] < a[i].z) continue;
      fa[fx] = fy; get(fx); s[fy] = a[i].z;
    }
    rep(i, 0, n - 1) p[get(i)].push_back(i);
    rep(i, 0, n - 1) sort(p[i].begin(), p[i].end());
    sort(p, p + n, cmp);
    rep(i, 0, n - 1)
    {
      if (p[i].size())
      {
        for (int j = 0; j < p[i].size(); j++)
        {
          printf("%s%d", j ? " " : "", p[i][j]);
        }
        putchar(10);
      }
    }
  }
  return 0;
}