首页 > ACM题库 > HDU-杭电 > hdu 3749 Financial Crisis[解题报告]C++
2015
02-22

hdu 3749 Financial Crisis[解题报告]C++

Financial Crisis

问题描述 :

Because of the financial crisis, a large number of enterprises go bankrupt. In addition to this, other enterprises, which have trade relation with the bankrup enterprises, are also faced with closing down. Owing to the market collapse, profit decline and funding chain intense, the debt-ridden entrepreneurs
have to turn to the enterprise with stably developing for help.
Equivalent mass

Nowadays, there exist a complex net of financial trade relationship between enterprises. So if one of enterprises on the same financial chain is faced with bankrupt, leading to cashflow’s obstruction, the other enterprises related with it will be influenced as well. At the moment, the foresight entrepreneurs are expected the safer cooperation between enterprises. In this sense, they want to know how many financial chains between some pairs of enterprises are independent with each other. The indepence is defined that if there exist two roads which are made up of enterprises(Vertexs) and their financial trade relations(Edge) has the common start point S and end point T, and expect S and T, none of other enterprise in two chains is included in these two roads at the same time. So that if one of enterpirse bankrupt in one of road, the other will not be obstructed.Now there are N enterprises, and have M pair of financial trade relations between them, the relations are Mutual. They need to ask about Q pairs of enterprises’ safety situations. When two enterprises have two or more independent financial chains, we say they are safe enough, you needn’t provide exact answers.

输入:

The Input consists of multiple test cases. The first line of each test case contains three integers, N ( 3 <= N <= 5000 ), M ( 0 <= M <= 10000 ) and Q ( 1 <= Q <= 1000 ). which are the number of enterprises, the number of the financial trade relations and the number of queries.
The next M lines, each line contains two integers, u, v ( 0 <= u, v < N && u != v ), which means enterpirse u and enterprise v have trade relations, you can assume that the input will not has parallel edge.
The next Q lines, each line contains two integers, u, v ( 0 <= u, v < N && u != v ), which means entrepreneurs will ask you the financial safety of enterpirse u and enterprise v.
The last test case is followed by three zeros on a single line, which means the end of the input.

输出:

The Input consists of multiple test cases. The first line of each test case contains three integers, N ( 3 <= N <= 5000 ), M ( 0 <= M <= 10000 ) and Q ( 1 <= Q <= 1000 ). which are the number of enterprises, the number of the financial trade relations and the number of queries.
The next M lines, each line contains two integers, u, v ( 0 <= u, v < N && u != v ), which means enterpirse u and enterprise v have trade relations, you can assume that the input will not has parallel edge.
The next Q lines, each line contains two integers, u, v ( 0 <= u, v < N && u != v ), which means entrepreneurs will ask you the financial safety of enterpirse u and enterprise v.
The last test case is followed by three zeros on a single line, which means the end of the input.

样例输入:

3 1 2
0 1
0 2
1 0
4 4 2
0 1
0 2
1 2
2 3
1 2
1 3
0 0 0

样例输出:

Case 1:
zero
one
Case 2:
two or more
one


给一个无向图, n <5000, m < 10000
然后给出若干的询问(< 1000),问一个点到另一个点之间有多少条路可以走,只需回答有0条还是1条还是多条。注意这些路之间不能有边相同。

方法:
求点的双连通分量。
然后一个割点,有可能属于多个点双连通分量。
所以我们要是用vector把每个点属于的点双连通分量的编号都存起来。
然后我们要计算每个点双连通分量中的边的个数。 因为有那种只有一条边的双连通分量。
计算的方法就是查看边得两个端点所属的双连通分量,如果两个端点有同属于的一个双连通分量,就把对应的数目加1

对于每个询问。
首先看两个点是否连通。用并查集判断即可
然后看是否同属于一个双连通分量。 不属于就只能有一条路
然后同属于一个双连通分量的话,就看边得个数是否大于1。即可

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <map>
#include <sstream>
#include <queue>
#include <vector>
#define MAXN 111111
#define MAXM 211111
#define eps 1e-8
#define INF 1000000001
using namespace std;
int e, tmpdfn, top;
int n, m, ind;
int vis[MAXM], head[MAXN], dfn[MAXN], low[MAXN], num[MAXM];
vector<int>g[MAXN];
struct Edge
{
    int v, next;
}edge[MAXM];
void add(int u, int v)
{
    edge[e].v = v;
    edge[e].next = head[u];
    head[u] = e++;
    edge[e].v = u;
    edge[e].next = head[v];
    head[v] = e++;
}
struct Stack
{
    int s, e;
    Stack(){}
    Stack(int a, int b){s = a; e = b;}
}st[MAXM];
void init()
{
    e = tmpdfn = ind = 0;
    top = -1;
    memset(vis, 0, sizeof(vis));
    memset(dfn, 0, sizeof(dfn));
    memset(head, -1, sizeof(head));
    memset(num, 0, sizeof(num));
}
void color(Stack t)
{
    ind++;
    while(top >= 0)
    {
        Stack A = st[top--];
        g[A.s].push_back(ind);
        g[A.e].push_back(ind);
        if(A.s == t.s && A.e == t.e) break;
    }
}
void dfs(int u, int fa)
{
    dfn[u] = low[u] = ++tmpdfn;
    for(int i = head[u]; i != -1; i = edge[i].next)
    {
        int v = edge[i].v;
        if(vis[i] == 0)
        {
            vis[i] = vis[i ^ 1] = 1;
            Stack tmp(u, v);
            st[++top] = tmp;
            if(!dfn[v])
            {
                dfs(v, u);
                low[u] = min(low[u], low[v]);
                if(low[v] >= dfn[u]) color(tmp);
            }
            else if(v != fa) low[u] = min(low[u], dfn[v]);
        }
    }
}
int Q;
int uu[MAXM], vv[MAXM];
int fa[MAXN];
int find(int x)
{
    if(fa[x] == x) return x;
    int t = find(fa[x]);
    fa[x] = t;
    return t;
}
void join(int u, int v)
{
    int fx = find(u);
    int fy = find(v);
    if(fx != fy) fa[fx] = fy;
}
int main()
{
    int u, v;
    int cas = 0;
    while(scanf("%d%d%d", &n, &m, &Q) != EOF)
    {
        if(n == 0 && m == 0 && Q == 0) break;
        init();
        for(int i = 1; i <= n; i++) fa[i] = i;
        for(int i = 0; i < m; i++)
        {
            scanf("%d%d", &uu[i], &vv[i]);
            uu[i]++; vv[i]++;
            add(uu[i], vv[i]);
            join(uu[i], vv[i]);
        }
        for(int i = 1; i <= n; i++) g[i].clear();
        for(int i = 1; i <= n; i++)
        {
            if(!dfn[i]) dfs(i, 0);
        }
        for(int i = 1; i <= n; i++) sort(g[i].begin(), g[i].end());
        for(int i = 1; i <= n; i++) unique(g[i].begin(), g[i].end());

        for(int i = 0; i < m; i++)
        {
            int sz1 = g[uu[i]].size();
            int sz2 = g[vv[i]].size();
            int k1 = 0, k2 = 0;
            while(k1 < sz1 && k2 < sz2)
            {
                if(g[uu[i]][k1] > g[vv[i]][k2]) k2++;
                else if(g[uu[i]][k1] < g[vv[i]][k2]) k1++;
                else if(g[uu[i]][k1] == g[vv[i]][k2])
                {
                    int tmp = g[uu[i]][k1];
                    num[tmp]++;
                    break;
                }
            }
        }
        printf("Case %d:\n", ++cas);
        for(int i = 0; i < Q; i++)
        {
            scanf("%d%d", &u, &v);
            u++; v++;
            int sz1 = g[u].size();
            int sz2 = g[v].size();
            int k1 = 0, k2 = 0;
            int tmp = -1;
            while(k1 < sz1 && k2 < sz2)
            {
                if(g[u][k1] > g[v][k2]) k2++;
                else if(g[u][k1] < g[v][k2]) k1++;
                else if(g[u][k1] == g[v][k2])
                {
                    tmp = g[u][k1];
                    break;
                }
            }
            if(find(u) != find(v)) puts("zero");
            else if(tmp == -1) puts("one");
            else if(num[tmp] == 1) puts("one");
            else puts("two or more");
        }
    }
    return 0;
}

 


  1. 给你一组数据吧:29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的,耗时却不短。这种方法确实可以,当然或许还有其他的优化方案,但是优化只能针对某些数据,不太可能在所有情况下都能在可接受的时间内求解出答案。