首页 > ACM题库 > HDU-杭电 > hdu 2647 Reward-拓扑排序-[解题报告]C++
2014
02-12

hdu 2647 Reward-拓扑排序-[解题报告]C++

Reward

问题描述 :

Dandelion’s uncle is a boss of a factory. As the spring festival is coming , he wants to distribute rewards to his workers. Now he has a trouble about how to distribute the rewards.
The workers will compare their rewards ,and some one may have demands of the distributing of rewards ,just like a’s reward should more than b’s.Dandelion’s unclue wants to fulfill all the demands, of course ,he wants to use the least money.Every work’s reward will be at least 888 , because it’s a lucky number.

输入:

One line with two integers n and m ,stands for the number of works and the number of demands .(n<=10000,m<=20000)
then m lines ,each line contains two integers a and b ,stands for a’s reward should be more than b’s.

输出:

One line with two integers n and m ,stands for the number of works and the number of demands .(n<=10000,m<=20000)
then m lines ,each line contains two integers a and b ,stands for a’s reward should be more than b’s.

样例输入:

2 1
1 2
2 2
1 2
2 1

样例输出:

1777
-1

这道题不能用矩阵表示,因为1w*1w绝对超内存,分析数据,前一个a的钱要多于后一个b,所以我们要把b作为出度,a为入度,如果不明白这个地方,举例:b——>a——>c——>d ,b为888,钱数逐渐上升,如果反过来a为出度就不符合题意啦。。。

还有一个地方需要注意:判断输出-1的情况不能只判断没有一个入度为0的点,因为有可能在中间就出现矛盾了,如:a——>b——>c——>d——>c 有入度为0的点,但却要输出-1;

#include<iostream>
#include<cstring>
#include<queue>
#include<cstdio>
using namespace std;
#define MAX 10005
int n,sum,ans;
int into[MAX],head[MAX],money[MAX];
struct Reward
{
    int to;
    int next;
} edge[2*MAX];
void topu()
{
    int i,j,l,v;
    queue<int>Q;
    for(i=1; i<=n; i++)
        if(into[i]==0)
            Q.push(i);//把入度为0的点压如队列
    while(!Q.empty())
    {
        v=Q.front();//调用首位元素
        sum+=money[v];
        Q.pop();//出队
        ans++; //用一个变量记录调用元素的总量,最后与n作比较
        for(l=head[v]; l!=-1; l=edge[l].next)//与队首元素v有关的都枚举一遍
        {
            if(--into[edge[l].to]==0)//如果入度-1为0,即为v的下一个元素
            {
                Q.push(edge[l].to);//将其压入队列
                money[edge[l].to]=money[v]+1;//保证后一个要比前一个多1
            }
        }

    }
}
int main()
{
    int m,a,b,tot;
    while(scanf("%d%d",&n,&m)!=EOF)
    {

        memset(head,-1,sizeof(head));
        memset(into,0,sizeof(into));
        for(int i=1; i<=n; i++)
            money[i]=888;//所有人一开始都为888
        tot=0;
        sum=0;
        ans=0;
        while(m--)
        {
            scanf("%d%d",&a,&b);//注意要逆过来,因为后一个b是基础的888,应当作为出度
            edge[tot].to=a;
            edge[tot].next=head[b];
            head[b]=tot++;
            into[a]++;//记录入度
        }
        topu();
        if(ans!=n)//有可能在中间出现矛盾,必须保证每个地方都不矛盾
            sum=-1;
        cout<<sum<<endl;

    }

}

解题转自:http://blog.csdn.net/u011538668/article/details/10537195


  1. /*
    * =====================================================================================
    *
    * Filename: 1366.cc
    *
    * Description:
    *
    * Version: 1.0
    * Created: 2014年01月06日 14时52分14秒
    * Revision: none
    * Compiler: gcc
    *
    * Author: Wenxian Ni (Hello World~), [email protected]
    * Organization: AMS/ICT
    *
    * =====================================================================================
    */

    #include
    #include

    using namespace std;

    int main()
    {
    stack st;
    int n,i,j;
    int test;
    int a[100001];
    int b[100001];
    while(cin>>n)
    {
    for(i=1;i>a[i];
    for(i=1;i>b[i];
    //st.clear();
    while(!st.empty())
    st.pop();
    i = 1;
    j = 1;

    while(in)
    break;
    }
    while(!st.empty()&&st.top()==b[j])
    {
    st.pop();
    j++;
    }
    }
    if(st.empty())
    cout<<"YES"<<endl;
    else
    cout<<"NO"<<endl;
    }
    return 0;
    }

  2. 如果两个序列的最后字符不匹配(即X [M-1]!= Y [N-1])
    L(X [0 .. M-1],Y [0 .. N-1])= MAX(L(X [0 .. M-2],Y [0 .. N-1]),L(X [0 .. M-1],Y [0 .. N-1])
    这里写错了吧。