A、POJ3159 Candies
题目描述
During the kindergarten days, flymouse was the monitor of his class. Occasionally the head-teacher brought the kids of flymouse’s class a large bag of candies and had flymouse distribute them. All the kids loved candies very much and often compared the numbers of candies they got with others. A kid A could had the idea that though it might be the case that another kid B was better than him in some aspect and therefore had a reason for deserving more candies than he did, he should never get a certain number of candies fewer than B did no matter how many candies he actually got, otherwise he would feel dissatisfied and go to the head-teacher to complain about flymouse’s biased distribution.snoopy shared class with flymouse at that time. flymouse always compared the number of his candies with that of snoopy’s. He wanted to make the difference between the numbers as large as possible while keeping every kid satisfied. Now he had just got another bag of candies from the head-teacher, what was the largest difference he could make out of it?
输入格式
The input contains a single test cases. The test cases starts with a line with two integers N and M not exceeding 30 000 and 150 000 respectively. N is the number of kids in the class and the kids were numbered 1 through N. snoopy and flymouse were always numbered 1 and N. Then follow M lines each holding three integers A, B and c in order, meaning that kid A believed that kid B should never get over c candies more than he did.
输出格式
Output one line with only the largest difference desired. The difference is guaranteed to be finite.
样例
Sample Input
2 2
1 2 5
2 1 4
Sample Output
5
提示
32-bit signed integer type is capable of doing all arithmetic.
分析
题意：班上有n个同学，现在有一些糖要分给他们，设第i个同学得到的糖为p[i]，分糖必须满足条件：第i个同学要求第j个同学的糖不能超过自己k个，即p[j] - p[i] <= k，k >= 0。要求在满足这些条件的情况下，求出p[n] - p[1]的最大值。
解法就是差分约束建图，如果p[j] - p[i] <= k，那么就从i到j建一条边权为k的有向边
之后再跑一个最短路就可以了
代码
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int maxf=30010,maxn=150010;
bool vis[maxf];
struct asd{
int from;
int to;
int data;
int next;
asd(){
from=0,to=0,data=0,next=0;
}
}bian[maxn];
int head[maxn];
int tot=1;
void ad(int a,int b,int c){
bian[tot].from=a,bian[tot].to=b,bian[tot].data=c;
bian[tot].next=head[a],head[a]=tot;tot++;
}
struct jie{
int num;
int dis;
jie(int a=0,int b=0){
num=a,dis=b;
}
bool operator < (const jie& a) const{
return dis>a.dis;
}
};
priority_queue<jie> q;
int dis[maxf];
void solve(){
q.push(jie(1,0));
memset(dis,0x3f,sizeof(dis));
dis[1]=0;
while(!q.empty()){
jie a=q.top();
q.pop();
if(vis[a.num]==true) continue;
vis[a.num]=true;
for(int i=head[a.num];i>0;i=bian[i].next){
int u=bian[i].to;
if(dis[u]>bian[i].data+dis[a.num]){
dis[u]=bian[i].data+dis[a.num];
q.push(jie(u,dis[u]));
}
}
}
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
memset(head,-1,sizeof(head));
for(int i=1;i<=m;i++){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
ad(a,b,c);
}
solve();
printf("%d\n",dis[n]);
return 0;
}
B、POJ 3660 Cow Contest
题目描述
N (1 ≤ N ≤ 100) cows, conveniently numbered 1..N, are participating in a programming contest. As we all know, some cows code better than others. Each cow has a certain constant skill rating that is unique among the competitors.
The contest is conducted in several head-to-head rounds, each between two cows. If cow A has a greater skill level than cow B (1 ≤ A ≤ N; 1 ≤ B ≤ N; A ≠ B), then cow A will always beat cow B.
Farmer John is trying to rank the cows by skill level. Given a list the results of M (1 ≤ M ≤ 4,500) two-cow rounds, determine the number of cows whose ranks can be precisely determined from the results. It is guaranteed that the results of the rounds will not be contradictory.
输入格式
* Line 1: Two space-separated integers: N and M
* Lines 2..M+1: Each line contains two space-separated integers that describe the competitors and results (the first integer, A, is the winner) of a single round of competition: A and B
输出格式
Line 1: A single integer representing the number of cows whose ranks can be determined
样例
Sample Input
5 5
4 3
4 2
3 2
1 2
2 5
Sample Output
2
分析
题意：给出m对牛的相互关系，求有多少个牛排名是确定的。
如果两个牛之间的排名是确定的，那么就把它们之间的边权设为1
最后跑一个最短路，如果一个点到其它点的距离都是确定的，那么它的排名也就确定了
数据范围比较小，用Floyd
代码
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int maxn=110;
int f[maxn][maxn];
bool vis[maxn];
int main(){
memset(f,0x3f,sizeof(f));
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int a,b;
scanf("%d%d",&a,&b);
f[a][b]=1;
}
for(int i=1;i<=n;i++)
f[i][i]=1;
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
if(f[i][j]==0x3f3f3f3f && f[j][i]==0x3f3f3f3f){
vis[i]=1,vis[j]=1;
}
int ans=n;
for(int i=1;i<=n;i++) ans-=vis[i];
printf("%d\n",ans);
return 0;
}