2014
02-12

# 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

#include<iostream>
#include<cstring>
#include<queue>
#include<cstdio>
using namespace std;
#define MAX 10005
int n,sum,ans;
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作比较
{
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(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;
into[a]++;//记录入度
}
topu();
if(ans!=n)//有可能在中间出现矛盾，必须保证每个地方都不矛盾
sum=-1;
cout<<sum<<endl;

}

}

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]）
这里写错了吧。