首页 > ACM题库 > HDU-杭电 > HDU 3357-Stock Chase[解题报告]HOJ
2014
03-16

HDU 3357-Stock Chase[解题报告]HOJ

Stock Chase

问题描述 :

I have to admit, the solution I proposed last year for solving the bank cash crisis didn’t solve the whole economic crisis. As it turns out, companies don’t have that much cash in the first place.
They have assets which are primarily shares in other companies. It is common, and acceptable, for one company to own shares in another. What complicates the issue is for two companies to own shares in each other at the same time. If you think of it for a moment, this means that each company now (indirectly) controls its own shares.
New market regulation is being implemented: No company can control shares in itself, whether directly or indirectly. The Stock Market Authority is looking for a computerized solution that will help it detect any buying activity that will result in a company controlling its own shares. It is obvious why they need a program to do so, just imagine the situation where company A buying shares in B, B buying in C, and then C buying in A. While the first two purchases are acceptable.
The third purchase should be rejected since it will lead to the three companies controlling shares in themselves. The program will be given all purchasing transactions in chronological order. The program should reject any transaction that could lead to one company controlling its own shares.
All other transactions are accepted.

输入:

Your program will be tested on one or more test cases. Each test case is specified on T + 1 lines. The first line specifies two positive numbers: (0 < N <= 234) is the number of companies and (0 < T <= 100, 000) is the number of transactions. T lines follow, each describing a buying transaction. Each transaction is specified using two numbers A and B where (0 < A,B <= N) indicating that company A wants to buy shares in company B.
The last line of the input file has two zeros.

输出:

Your program will be tested on one or more test cases. Each test case is specified on T + 1 lines. The first line specifies two positive numbers: (0 < N <= 234) is the number of companies and (0 < T <= 100, 000) is the number of transactions. T lines follow, each describing a buying transaction. Each transaction is specified using two numbers A and B where (0 < A,B <= N) indicating that company A wants to buy shares in company B.
The last line of the input file has two zeros.

样例输入:

3 6
1 2
1 3
3 1
2 1
1 2
2 3
0 0

样例输出:

1. 2

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3357

Stock Chase

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <queue>
#include <vector>

#define maxn 250
#define maxe 100050
#define INF  0x3f3f3f
using namespace std;

int N,T;
int ans;
bool G[maxn][maxn];
int l[maxn];
int r[maxn];
int lhead,ltail,rhead,rtail;
int main()
{
    //freopen("input.txt","r",stdin); 
    int t=1;
    while(scanf("%d%d",&N,&T) && N + T){
        memset(G,0,sizeof(G));
        ans = 0;
        for(int i=1;i<=T;i++){
            int u,v;
            scanf("%d%d",&u,&v);
            if(G[v][u] || u == v){
                ans++;
                continue;
            }
            G[u][v] = 1;
            lhead = ltail = rhead = rtail = 0;
            for(int i=1;i<=N;i++){
                if(G[i][u]) {G[i][v] = 1; l[ltail++] = i;}
                if(G[v][i]) {G[u][i] = 1; r[rtail++] = i;}        
            }
            for(int j=lhead;j<ltail;j++)
                   for(int k=rhead;k<rtail;k++){
                         G[l[j]][r[k]] = 1; 
                   }      
        }
        printf("%d. %d\n",t++,ans);
    }
}

View Code

 

参考:http://www.cnblogs.com/acmdeweilai/p/3235877.html


  1. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。

  2. Thanks for taking the time to examine this, I really feel strongly about it and love studying a lot more on this topic. If possible, as you acquire experience