[POJ 3463] 最短路变形 求方案数

【题目大意】给定一个有向图,求从S走到F(最短路)和(最短路长度+1)的方案总和。

【算法分析】用dijkstra+heap求出最短路和次短路的方案和长度。如果最短路和次短路的长度相差1,那么将方案数相加,否则直接输出

【其它】1A

【程序】

#include #include #include #define E 11111
#define N 1111*2
#define INF 0x7FFFFFFF/2
using namespace std;
struct gtp{int x,y,w,next;}g[E];
int ls[N],d[N],c[N],list[N],n,e,st,ed,zz[N];
struct headtpy{
       int a[N],tot;
       void up(int k){
            while (k>1 && d[a[k]]                  swap(a[k],a[k/2]);
                  zz[a[k]]=k; zz[a[k/2]]=k/2;
                  k/=2;
            }
       }
       void down(int k){
            while (k*2<=tot){
                  int t=k*2;
                  if (t+1<=tot && d[a[t+1]]                  if (d[a[k]]>d[a[t]]){
                    swap(a[k],a[t]);
                    zz[a[k]]=k; zz[a[t]]=t;
                    k=t;
                  }
                  else break;
            }
       }
       void ins(int locate){
            tot++;
            a[tot]=locate;
            zz[locate]=tot;
            up(tot);
       }
       void del(){
            a[1]=a[tot];
            tot--;
            down(1);
       }
}heap;

void init(){
     scanf("%d%d",&n,&e);
     memset(ls,0,sizeof(ls));
     memset(zz,0,sizeof(zz));
     for (int i=1;i<=e;i++){
         int x,y,w;
         scanf("%d%d%d",&g[i].x,&g[i].y,&g[i].w);
         g[i].next=ls[g[i].x]; ls[g[i].x]=i;
     }
     scanf("%d%d",&st,&ed);
     for (int i=1;i<=2*n;i++){
         d[i]=INF;
         c[i]=0;
     }
     d[st*2-1]=0; c[st*2-1]=1;
     heap.tot=0;
     for (int i=1;i<=2*n;i++) heap.ins(i);
}

inline void push(int td,int tc,int ty){
       if (td         d[ty*2]=d[ty*2-1];
         c[ty*2]=c[ty*2-1];
         heap.up(zz[ty*2]);
         d[ty*2-1]=td;
         c[ty*2-1]=tc;
         heap.up(zz[ty*2-1]);
       }
       else if (td==d[ty*2-1]) c[ty*2-1]+=tc;
       else if (td              d[ty*2]=td;
              c[ty*2]=tc;
              heap.up(zz[ty*2]);
            }
       else if (td==d[ty*2]) c[ty*2]+=tc;
}

void dijkstra(){
     while (heap.tot>0){
           int p=(heap.a[1]+1)/2;
           for (int t=ls[p];t!=0;t=g[t].next)
             push(d[heap.a[1]]+g[t].w,c[heap.a[1]],g[t].y);
           heap.del();
     }
     if (d[ed*2-1]+1==d[ed*2]) printf("%dn",c[ed*2-1]+c[ed*2]);
                          else printf("%dn",c[ed*2-1]);
}

int main(){
//    freopen("input.txt","r",stdin);
//    freopen("output.txt","w",stdout);
    int tc;
    scanf("%d",&tc);
    for (int i=1;i<=tc;i++){
        init();
        dijkstra();
    }
}

[UVA10246] 巧妙优化 最短路 打表

【题目来源】http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=14&page=show_problem&problem=1187

看不到的请用firefox浏览器。

【题目大意】给出一个无向图,点有点权,边有边权。然后有Q个询问(X,Y),表示求一条从X到Y的路径,其总代价为路上边权只和加上路径上点权最大的一个点的点权。询问就使这个总代价最少是多少?

【算法分析】

翻开《算法艺术与信息学竞赛》第308页就有这个题目。

我们假定了K为点权最大的点,那么显然,对于询问(X,Y):W=D[X,K]+D[K,Y]+COST[K]。

其中D[X,K]和D[K,Y]表示删除权值比K大的点以后的最短路。

由于是无向图,再转变一下。

W=D[K,X]+D[K,Y]+COST[K]。

到了这一步。。。大家都知道怎么打表了吧。。。

我们就先预处理出D[i,j]表示从第i个出发,且所有点权>COST[i]的点都已删掉以后,到达j的最短路。

这可以用SPFA实现,复杂度O(NM)

然后打表,复杂度O(N^3)

【其他】我居然WA了4次,因为同一个问题:我把Case #xxx看成是题目给的方便你看的。。。没有输出。。。我那叫一个纠结吖~拿块豆腐撞死自己算了

【code】

#include #include #include #include #define INF 0x7FFFFFFF
#define E 1000000
#define N 1000
using namespace std;
struct gtp{int x,y,w,next;}g[E];
int n,m,q,e,ls[N],ans[N][N],Vp[N],dist[N][N];
int d[N],list[N],v[N];

void add(int x,int y,int w){
    e++;
    g[e].x=x; g[e].y=y; g[e].w=w; g[e].next=ls[x]; ls[x]=e;
}

void init(){
    memset(ls,0,sizeof(ls));
    for (int i=1;i<=n;i++) scanf("%d",&Vp[i]);
    e=0;
    for (int i=1;i<=m;i++){
        int x,y,w;
        scanf("%d%d%d",&x,&y,&w);
        add(x,y,w);
        add(y,x,w);
    }
}

void spfa(int st){
    int head=0,tail=1; list[1]=st;
    memset(v,0,sizeof(v));
    for (int i=1;i<=n;i++) d[i]=INF;
    d[st]=0; v[st]=1;
    while (head!=tail){
        head++; if (head>=N) head=0;
        for (int t=ls[list[head]];t!=0;t=g[t].next)
          if (Vp[g[t].y]<=Vp[st] && d[g[t].x]+g[t].w              d[g[t].y]=d[g[t].x]+g[t].w;
              if (v[g[t].y]==0){
                  v[g[t].y]=1;
                  tail++; if (tail>=N) tail=0;
                  list[tail]=g[t].y;
              }
        }
        v[list[head]]=0;
    }
}

void work(){
    for (int i=1;i<=n;i++){
        spfa(i);
        for (int j=1;j<=n;j++) dist[i][j]=d[j];
    }
    for (int i=1;i<=n;i++)
      for (int j=1;j<=n;j++)
        ans[i][j]=INF;
    for (int i=1;i<=n;i++)
      for (int j=1;j<=n;j++)
        for (int k=1;k<=n;k++){
          int tmp;
          if (dist[k][i]==INF || dist[k][j]==INF) tmp=INF;
          else tmp=dist[k][i]+dist[k][j]+Vp[k];
          ans[i][j]=min(ans[i][j],tmp);
        }
    for (int i=1;i<=n;i++)
      for (int j=1;j<=n;j++)
        if (ans[i][j]==INF) ans[i][j]=-1;
}

void print(){
    for (int i=1;i<=q;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        printf("%dn",ans[x][y]);
    }
}

int main(){
    int test=0;
    for (;;){
        scanf("%d%d%d",&n,&m,&q);
        if (n+m+q==0) break;
        test++;
        if (test>1) printf("n");
        init();
        work();
        printf("Case #%dn",test);
        print();
    }
    return 0;
}

[POJ1062 昂贵的聘礼] 最短路

【题目大意】N个点,向起点连一条权值为T的弧,然后根据描述将图连出来,求起点到点1的最短路。不过,每个点有一个等级限制,这条最短路上的最大等级和最小等级差不能超过M。

【算法分析】枚举一个等级范围,然后spfa即可。以前用topsort写的那个是错的= =。。。如果真的用topsort+dp的话还要缩点。。。

【其他】1A

【code】

#include

[POJ 3565] 最小费用流 利用重要性质

【题目大意】:给定2*N个点的坐标,让你用前N个点和后N个点一一配对,使得相连的边没有相交的。

【算法分析】:首先有一个性质必须知道,那就是最短的配对,必然是没有相交的。于是我们就可以构建二分图,求最小权匹配。(用最小费用流求解)

【code】

#include

[HDOJ 1914] 稳定婚姻系统

题意:

就是稳定婚姻系统的模板题。

对于求出来的每一组配对(a,b),不能找到(b,c)满足b更喜欢c且c更喜欢b,对于a同样。

分析:

就使一种延迟方法,就使先让他们拍拖然后遇到更好的,就飞掉之前的伴侣。。。

有点邪恶。。。

更详细的讲解请参照:http://hi.baidu.com/leokan/blog/item/4f9b04f719993025730eecef.html

HINT:

1A。

code:

#include #include using namespace std;
int n,ml[27][27],fl[27][27],st[27],bf[27],gf[27],rank[27][27];
char mn[27],fn[27];

int pos(char ch){
    if (ch>='a' && ch<='z'){
      for (int i=1;i<=n;i++)
        if (mn[i]==ch) return i;
    }else   
      for (int i=1;i<=n;i++)
        if (fn[i]==ch) return i;
}

void init(){
    cin >> n;
    for (int i=1;i<=n;i++) cin >> mn[i];
    for (int i=1;i<=n;i++) cin >> fn[i];
    for (int t=1;t<=n;t++){
        char ch;
        cin >> ch;
        int i=pos(ch);
        cin >> ch;
        for (int j=1;j<=n;j++){
            cin >> ch;
            ml[i][j]=pos(ch);
        }   
    }   
    for (int t=1;t<=n;t++){
        char ch;
        cin >> ch;
        int i=pos(ch);
        cin >> ch;
        for (int j=1;j<=n;j++){
            cin >> ch;
            fl[i][j]=pos(ch);
        }   
    }   
    for (int i=1;i<=n;i++)
      for (int j=1;j<=n;j++)
        rank[i][fl[i][j]]=j;
}   

void dfs(int p){
    int i;
    for (i=st[p]+1;i<=n;i++){
        if (bf[ml[p][i]]==0){
            bf[ml[p][i]]=p;
            gf[p]=ml[p][i];
            break;
        }   
        if (rank[ml[p][i]][p]            int tmp=bf[ml[p][i]];
            bf[ml[p][i]]=p;
            gf[p]=ml[p][i];
            dfs(tmp);
            break;
        }   
    }  
    st[p]=i;
}   

void work(){
    memset(st,0,sizeof(st));
    memset(bf,0,sizeof(bf));
    memset(gf,0,sizeof(gf));
    for (int i=1;i<=n;i++)
      if (gf[i]==0) dfs(i);
}   

void print(){
    for (int i=1;i<=n;i++)
      cout << mn[i] << " " << fn[gf[i]] << endl;
}   

int main(){
    int T;
    cin >> T;
    for (int i=1;i<=T;i++){
        init();
        work();
        print();
        if (i!=T) cout << endl;
    }   
}