投資錢景>買台積電就對了三星平板★瘋殺5290起輕忽小中風,當心變殘障老伯送飲料 遭學生糾察...
2013-06-04 08:04:06 人氣(23) | 回應(0) | 推薦(0) | 收藏(0) 上一篇 | 下一篇

[UVA][圖論] 11550 - Demanding Dilemma

0
收藏
0
推薦

Problem D

DEMANDING DILEMMA

A simple undirected graph is an ordered pair G = (V, E) where V is a non-empty set of vertices, and E is a set of unordered pairs (u, v) where u and v are in V and u v. If S is a set, define |S| as the size of S. An incidence matrix M is a |V| x |E| matrix where M(i, j) is 1 if edge j is incident to vertex i (edge j is either (i, u) or (u, i)) and 0 otherwise.

Given an n x m matrix, can it be an incidence matrix of a simple undirected graph G = (V, E) where |V| = n and |E| = m?

Program Input

The first line of the input contains an integer t (1 ≤ t ≤ 41), the number of test cases.

Each test case starts with a line with two integers n (1 ≤ n ≤ 8) and m (0 ≤ m n(n-1)/2). Then n lines containing m integers (0’s or 1’s) each follow such that the jth number on the ith line is M(i, j).

Program Output

For each test case print “Yes” if the incidence matrix given in the input can be an incidence matrix of some simple undirected graph, otherwise print “No”.

Sample Input & Output

INPUT

3
3 3
1 1 0
0 1 1
1 0 1
3 1
1
1
0
3 3
1 1 0
1 1 1
1 0 0
OUTPUT
Yes
Yes
No

Calgary Collegiate Programming Contest 2008

題目在描述離散數學中講的點邊記錄方式,
然後簡單它是否為一個簡單圖(無重邊)。

點邊記錄方式是這麼描述的的
------e1--e2--e3--e4--e5 ...
node1 0   0   1
node2 1   1   0
node3 1   0   1
node4 0   1   0 ...

表示這個點是否有在這邊的兩端點,因此邊不會同具有非兩個點的情況。
同時要檢驗是否有重邊。

#include <stdio.h>

int main() {
    int vg[10][100];
    int n, m, i, j;
    int testcase;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d %d", &n, &m);
        for(i = 0; i < n; i++)
            for(j = 0; j < m; j++)
                scanf("%d", &vg[i][j]);
        int g[10][10] = {}, err = 0, x, y;
        for(i = 0; i < m && !err; i++) {
            int cnt = 0;
            for(j = 0; j < n; j++) {
                if(vg[j][i]) {
                    if(cnt == 0)    x = j;
                    else            y = j;
                    cnt++;
                }
            }
            if(cnt != 2)    err = 1;
            else {
                if(g[x][y]) err = 1;
                g[x][y] = g[y][x] = 1;
            }
        }
        puts(err ? "No" : "Yes");
    }
    return 0;
}

 

11550Demanding Dilemma
台長:Morris
人氣(23) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA] 11508 - Life on Mars?
此分類上一篇:[UVA][dp] 11022 - String Factoring

我要回應
是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入以下數字 (ex:123)

(有*為必填)
詳全文