标签存档：图论

【题目大意】给定N个货币和M种兑换方式，问能否不断加钱？

【算法分析】用spfa算法判断有无正权回路。如果一个点进入队列超过N次。。。那就是有正权了。

【其它】注意精度要控制一下

【code】

#include #include #include #include using namespace std;
struct gtp{int x,y,next;double rate,sui;}g[201];
double d[101],sm;
int v[101],list[101],n,e,st,ls[101],insnum[101];

inline void addedge(int x,int y,double rate,double sui){
       e++;
       g[e].x=x; g[e].y=y; g[e].next=ls[x]; ls[x]=e;
       g[e].rate=rate; g[e].sui=sui;
}

void init(){
     int m; e=0;
     scanf("%d%d%d%lf",&n,&m,&st,&sm);
     for (int i=1;i<=m;i++){
         double rate,sui;
         int xx,yy;
         scanf("%d%d%lf%lf",&xx,&yy,&rate,&sui);
         addedge(xx,yy,rate,sui);
         scanf("%lf%lf",&rate,&sui);
         addedge(yy,xx,rate,sui);
     }
}

bool spfa(){
     memset(d,0,sizeof(d));
     memset(v,0,sizeof(v));
     memset(insnum,0,sizeof(insnum));
     v[st]=1; d[st]=sm; insnum[st]=1; list[0]=st;
     int head=-1,tail=0;
     while (head!=tail){
           head++; if (head>100) head=0;
           for (int t=ls[list[head]];t!=0;t=g[t].next)
             if ((d[g[t].x]-g[t].sui)*g[t].rate>=d[g[t].y]+1e-6){
               d[g[t].y]=(d[g[t].x]-g[t].sui)*g[t].rate;
               if (v[g[t].y]==0){
                 v[g[t].y]=1;
                 tail++; if (tail>100) tail=0;
                 list[tail]=g[t].y;
                 insnum[g[t].y]++;
                 if (insnum[g[t].y]>n) return true;
               }
             }
           v[list[head]]=0;
     }
     return false;
}

int main(){
    init();
    if (spfa()) printf("YESn");
           else printf("NOn");
}

【题目大意】给定一个有向图，求从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();
    }
}

【题目来源】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;
}

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

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

【其他】1A

【code】

#include

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

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

【code】

#include