http://acm.pku.edu.cn/JudgeOnline/problem?id=3159
比較變態(tài)的題目,還是sempr大牛出的題^-^!!
我只用spfa 踩點(diǎn)1500ms過(guò)了！用 dijkstra+heap TLE了！不知道是不是自己寫(xiě)的有問(wèn)題？
題目意思：
flymouse是幼稚園班上的班長(zhǎng)，一天老師給小朋友們買了一堆的糖果，由flymouse來(lái)分發(fā)，在班上，
flymouse和snoopy是死對(duì)頭，兩人勢(shì)如水火，不能相容，因此fly希望自己分得的糖果數(shù)盡量多于
snoopy，而對(duì)于其他小朋友而言，則只希望自己得到的糖果不少于班上某某其他人就行了。
比如A小朋友強(qiáng)烈希望自己的糖果數(shù)不能少于B小朋友m個(gè)，即B- A<=m，A，B分別為
A、B小朋友的分得的糖果數(shù)。這樣給出若干組這樣的條件，要使fly最后分得的糖果數(shù)s1和snoopy
最后分得的糖果數(shù)s2差別取到最大！即s2-s1取最大.
因此根據(jù)題意，可以列出如下的不等式：
Sbi-Sai<=ci(1=<i<=n)
最終要使得Sn-S1最大；
其實(shí)就是一個(gè)差分約束系統(tǒng)。
求最短路時(shí)用到的三角形不等式中，最終對(duì)于每條有向邊(u,v)有: d[v]<=d[u]+w(u,v);
將Sbi-Sai<=ci變成Sbi<=Sai+ci;就跟上式的形式相似。
在最短路的松弛過(guò)程中每次都是 if(d[v]>d[u]+w(u,v)) then d[v]<=d[u]+w(u,v);
則最后不斷的松弛，使得對(duì)所有邊 d[v]<=d[u]+w(u,v);
對(duì)于Sbi<=Sai+ci;通過(guò)做bellmanford，Sbi通過(guò)不斷的松弛,由正的無(wú)窮不斷減小，直到所有的
約束條件都的到滿足，所以這時(shí)的求出的Sbi是滿足約束條件的最大的一組解!!
這樣最后的結(jié)果就是Sn-S1，初始時(shí)將S1設(shè)為0，則最后的結(jié)果就是Sn的值!
不過(guò)直接用bellman-ford復(fù)雜度高了點(diǎn)！用隊(duì)列優(yōu)化的bellman-ford即spfa可以承受!
代碼寫(xiě)起來(lái)比較簡(jiǎn)潔
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();
}
}
另外附上我寫(xiě)的heap+dijkstra,總是超時(shí)，實(shí)在無(wú)語(yǔ),望哪位路過(guò)的大牛指點(diǎn)迷津！！
#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;
}