ACM – 浙江省赛F – 图论

点击量:25

  • 浙江省赛题目,分析后直接暴力即可,奈何场上脑子里全是floyd,WA无数次。

  • 做题一定要先分析时间复杂问题,采取暴力方法,然后再考虑复杂问题解决方法。

  • 此外今天开始使用赛用vimrc才发现出现不少问题,还好提前使用了。

#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
int n, m, k;
const int maxn = 100 +10;
int g[maxn][maxn];
void debug()
{
    for(int i = 0; i < n; i++)
    {
        for(int j = 0;j < n;j ++)
        {
            cout << g[i][j];
        }
        cout << endl;
    }
}
int main()
{
    //freopen("input", "r", stdin);
    int t;
    cin >> t;
    int u, v;
    while(t--)
    {
        memset(g, 0, sizeof(g));
        scanf("%d%d%d", &n, &m, &k);
        for(int i = 0; i < m; i++)
        {
            scanf("%d%d", &u, &v);
            g[u][v] = g[v][u] = 1;
        }
        int ans, pre;
        ans = 0;
        pre = 1;
        while(pre != ans) {
            pre = ans;
            for(int i = 0; i < n; i++) {
                for(int j = 0;j < n; j++) {
                    // itself
                    if(i == j || g[i][j]) continue;
                    int count = 0;
                    for(int s = 0; s < n; s++)
                        if(s != i && s != j && g[i][s] && g[s][j])
                            count++;
                    if(count >= k) {
                        ans++;
                        g[i][j] = 1;
                        g[j][i] = 1;
                    }
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注