首页 > ACM题库 > 九度OJ > 九度-1418-宝藏[解题代码]
2013
12-13

九度-1418-宝藏[解题代码]

题目描述:

        Luke 得到一张藏宝图,藏宝图上有n个城市(编号1-n),并且这些城市有一些道路相连着。每个城市里都有一份宝藏,并且宝藏图里已经把每个城市的宝藏位置描述得很清楚了,所以只要Luke能到达这个城市,他就一定能找到这个城市里的那份宝藏。

输入:

        输入有多组,每组输入第一行为三个整数n,m,s(1<=n<=100000,0<=m<=150000)。分别表示城市的数量数和连接这些城市的路径数量,s为Luke的起点城市。接下来是m对整数v,u(1<=v,u<=n),表示从v到u有一条路径(路径为单向的)。

输出:

        对于每组输入,先输出一行”Case T:” T从1开始。输出Luke最多能找到的宝藏数量。

样例输入:
4 3 1
1 2
2 3
2 4
5 4 1
1 2
2 3
2 4
3 2
样例输出:
Case 1:
3
Case 2:
4

cpp 代码如下:
#include<stack>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>

using namespace std;

const int N = 100005;
const int M = 150005;

struct Edge
{
    int u,v,link;
}edge[M];
stack<int> s;
vector<int> node[N];

int head[N],sz, start;
bool vis[N];
int dfn[N],low[N],blg[N],val[N];
int cnt,dindex;
int connNum,otherCnt,omax;

void tarjan(int u)
{
    dfn[u]=low[u]=++dindex;
    s.push(u);
    vis[u]=true;
    for(int j=head[u];j!=-1;j=edge[j].link)
    {
    	//cout << edge[j].u << " " << edge[j].v << " " << edge[j].link << endl;
        int v=edge[j].v;
        if(!dfn[v])
        {
            tarjan(v);
            if(low[u]>low[v]) low[u]=low[v];
        }
        else if(vis[v] && low[u]>dfn[v]) low[u]=dfn[v];
    }
    if(dfn[u]==low[u])
    {
        int c;
        cnt++;
        val[cnt]=0;
        otherCnt = 0;
        do
        {
            c=s.top();
            //cout << c << " < ";
            s.pop();
            vis[c]=false;
            blg[c]=cnt;
//            if(u == start){
//            	connNum ++;
//            }else
//            	otherCnt ++;
            val[cnt]++;
        }while(c!=u);
        //cout << endl << val[cnt] << endl;
    }
    if(otherCnt > omax) omax = otherCnt;
}
void init()
{
    memset(head,-1,sizeof(head));
    sz=0;
}
inline void edgeadd(int u,int v)
{
    edge[sz].u=u;
    edge[sz].v=v;
    edge[sz].link=head[u];
    head[u]=sz++;
}
void Dfs(int u,int value,int & ans)
{
    int v=value+val[u];
    ans=max(ans,v);
    for(unsigned int i=0;i<node[u].size();i++) Dfs(node[u][i],v,ans);
}
int main()
{
    int n,m,s,cas=0;
    while(~scanf("%d %d %d",&n,&m,&start))
    {
        init();
        int u,v;
        for(int i=1;i<=m;i++)
        {
            scanf("%d %d",&u,&v);
            edgeadd(u,v);
        }
        connNum = otherCnt = omax = 0;
        cnt=dindex=0;
        memset(dfn,0,sizeof(dfn));
        memset(vis,false,sizeof(vis));

        for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
       // tarjan(start);

        for(int i=1;i<=cnt;i++) node[i].clear();
        for(int i=0;i<sz;i++)
        {
            int u=blg[edge[i].u];
            int v=blg[edge[i].v];
            if(u!=v) node[u].push_back(v);
        }
        int ans=0;
        Dfs(blg[start],0,ans);
        printf("Case %d:\n%d\n",++cas,ans);
    }
    return 0;
}
/**************************************************************
	Problem: 1418
	User: coder
	Language: C++
	Result: Accepted
	Time:540 ms
	Memory:9548 kb
****************************************************************/


  1. 问题3是不是应该为1/4 .因为截取的三段,无论是否能组成三角形, x, y-x ,1-y,都应大于0,所以 x<y,基础应该是一个大三角形。小三角是大三角的 1/4.