http://acm.pku.edu.cn/JudgeOnline/problem?id=3159
比较变态的题目,还是sempr大牛出的题^-^!!
我只用spfa 踩点1500ms过了！用 dijkstra+heap TLE了！不知道是不是自己写的有问题？
题目意思：
flymouse是幼稚园班上的班长，一天老师给小朋友们买了一堆的糖果，由flymouse来分发，在班上，
flymouse和snoopy是死对头，两人势如水火，不能相容，因此fly希望自己分得的糖果数尽量多于
snoopy，而对于其他小朋友而言，则只希望自己得到的糖果不少于班上某某其他人就行了。
比如A小朋友强烈希望自己的糖果数不能少于B小朋友m个，即B- A<=m，A，B分别为
A、B小朋友的分得的糖果数。这样给出若干组这样的条件，要使fly最后分得的糖果数s1和snoopy
最后分得的糖果数s2差别取到最大！即s2-s1取最大.
因此根据题意，可以列出如下的不等式：
Sbi-Sai<=ci(1=<i<=n)
最终要使得Sn-S1最大；
其实就是一个差分约束系统。
求最短路时用到的三角形不等式中，最终对于每条有向边(u,v)有: d[v]<=d[u]+w(u,v);
将Sbi-Sai<=ci变成Sbi<=Sai+ci;就跟上式的形式相似。
在最短路的松弛过程中每次都是 if(d[v]>d[u]+w(u,v)) then d[v]<=d[u]+w(u,v);
则最后不断的松弛，使得对所有边 d[v]<=d[u]+w(u,v);
对于Sbi<=Sai+ci;通过做bellmanford，Sbi通过不断的松弛,由正的无穷不断减小，直到所有的
约束条件都的到满足，所以这时的求出的Sbi是满足约束条件的最大的一组解!!
这样最后的结果就是Sn-S1，初始时将S1设为0，则最后的结果就是Sn的值!
不过直接用bellman-ford复杂度高了点！用队列优化的bellman-ford即spfa可以承受!
代码写起来比较简洁
Source Code
| Problem: 3159 |
|
User: lovecanon |
| Memory: 6972K |
|
Time: 1500MS |
| Language: C++ |
|
Result: Accepted |
#include<stdio.h>
#include<string.h>
struct node{
int v,val;
node *next;
}edge[150001];
int n,m,dist[30001],mem[30001],s[30001],top;
void insert(int a,int b,int c){
node *s=new node;
s->v=b;s->val=c;
s->next=edge[a].next;
edge[a].next=s;
}
void spfa(){
memset(s,0,sizeof(s));
top=0;
mem[++top]=1;
memset(dist,127,sizeof(dist));
dist[1]=0;
s[1]=1;
while(top){
int cnt=mem[top--];
s[cnt]=0;
node *ptr=edge[cnt].next;
while(ptr){
int tmp=ptr->v;
if(dist[tmp]>dist[cnt]+ptr->val){
dist[tmp]=dist[cnt]+ptr->val;
if(!s[tmp]){
mem[++top]=tmp;
s[tmp]=1;
}
}
ptr=ptr->next;
}
}
printf("%d\n",dist[n]);
}
int main(){
int i,a,b,c;
while(scanf("%d%d",&n,&m)!=EOF){
memset(edge,0,sizeof(edge));
for(i=1;i<=m;i++){
scanf("%d%d%d",&a,&b,&c);
insert(a,b,c);
}
spfa();
}
}
另外附上我写的heap+dijkstra,总是超时，实在无语,望哪位路过的大牛指点迷津！！
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
struct node{
int v,val;
node *next;
}edge[150001];
struct Heap{
int v,val;
}heap[30001];
int n,m,dist[30001],s[30001],tail;
int get_min(int a,int b){if(a<=b) return a;else return b;}
void insert(int a,int b,int c){
node *s=new node;
s->v=b;s->val=c;
s->next=edge[a].next;
edge[a].next=s;
}
void heap_push(int v,int val){
heap[++tail].v=v;heap[tail].val=val;
int root=tail;
while(root/2){
if(heap[root/2].val>heap[root].val){
int tmp1,tmp2;
tmp1=heap[root].v;tmp2=heap[root].val;
heap[root].v=heap[root/2].v;heap[root].val=heap[root/2].val;
heap[root/2].v=tmp1;heap[root/2].val=tmp2;
}
root/=2;
}
}
int heap_pop(){
int res=heap[1].v;
heap[1].v=heap[tail].v;heap[1].val=heap[tail--].val;
int root=1,pos;
while((pos=root*2)<=tail){
if(pos+1<=tail&&heap[pos+1].val<heap[pos].val) pos++;
if(heap[root].val<heap[pos].val){
int tmp1,tmp2;
tmp1=heap[root].v;tmp2=heap[root].val;
heap[root].v=heap[pos].v;heap[root].val=heap[pos].val;
heap[pos].v=tmp1;heap[pos].val=tmp2;
root=pos;
}
}
return res;
}
void dijkstra(){
memset(dist,127,sizeof(dist));
memset(s,0,sizeof(s));
dist[1]=0;
s[1]=1;
tail=0;
heap_push(1,0);
while(tail){
int cnt=heap_pop(),id;
if(cnt==n) break;
s[cnt]=1;
node *ptr=edge[cnt].next;
while(ptr && !s[ptr->v]){
if(dist[ptr->v]>dist[cnt]+ptr->val){
dist[ptr->v]=dist[cnt]+ptr->val;
heap_push(ptr->v,dist[ptr->v]);
}
ptr=ptr->next;
}
}
printf("%d\n",dist[n]);
}
int main(){
while(scanf("%d%d",&n,&m)!=EOF){
memset(edge,0,sizeof(edge));
//memset(heap,127,sizeof(heap));
int i,a,b,c;
for(i=1;i<=m;i++){
scanf("%d%d%d",&a,&b,&c);
insert(a,b,c);
}
dijkstra();
}
return 0;
}