作者存档：edward_mj

【题目】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1491

【算法分析】

就是利用floyed求最短路。然后加多一个数组表示num[i][j]表示从i到j的最短路的数目。

然后在松弛的地方因为乘法原理，应当变成num[i][k]*num[k][j]，相等的话要加上方案。

最后统计一下就好了。

【其它】1A

【CODE】

#include using namespace std;
int n,m;
int d[122][122];
long long num[122][122];

void input(){
    memset(d,50,sizeof(d));
    memset(num,0,sizeof(num));
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++){
        int x,y,w;
        scanf("%d%d%d",&x,&y,&w);
        d[x][y]=w;
        d[y][x]=w;
        num[x][y]=1;
        num[y][x]=1;
    }   
}   

void floyed(){
    int i,j,k;
    for (k=1;k<=n;k++)
      for (i=1;i<=n;i++)
        for (j=1;j<=n;j++)
          if (i!=j && j!=k && i!=k){
              if (d[i][k]+d[k][j]                  d[i][j]=d[i][k]+d[k][j];
                  num[i][j]=num[i][k]*num[k][j];
              }   
              else if (d[i][k]+d[k][j]==d[i][j])
                  num[i][j]+=num[i][k]*num[k][j];
          }   
}   

void output(){
    int i,j,k;
    for (k=1;k<=n;k++){
        double ans=0;
        for (i=1;i<=n;i++)
          for (j=1;j<=n;j++)
            if (i!=j && j!=k && i!=k && d[i][j]==d[i][k]+d[k][j])
                ans+=num[i][k]*num[k][j]*1.0/num[i][j];
        printf("%.3lfn",ans);
    }   
}   

int main(){
    freopen("network.in","r",stdin);
    freopen("network.out","w",stdout);
    input();
    floyed();
    output();
}   

【题目大意】

参见NOIP的传纸条。

【算法分析】

直接费用流~

对于时间复杂度分析一下：由于只增广两次，所以复杂度是O(2*SPFA)。

不需要担心点太多了~

【CODE】

#include #include #include const int N=721111;
const int E=2160111;
const int INF=1000000000;
struct gtp{int x,y,next,op,w,c;}g[E];
int n,e,S,T,cost;
int pos[622][622],ls[N],d[N],v[N],list[N],fa[N];

inline void addedge(int x,int y,int c,int w){
    e++;
    g[e].x=x; g[e].y=y; g[e].c=c; g[e].w=w;
    g[e].next=ls[x]; ls[x]=e; g[e].op=e+1;
    e++;
    g[e].x=y; g[e].y=x; g[e].c=0; g[e].w=-w;
    g[e].next=ls[y]; ls[y]=e; g[e].op=e-1;
}   

void init(){
    int i,j,tmp=0,w;
    e=0;
    for (i=1;i<=2*n*n+2;i++) ls[i]=0;
    for (i=1;i<=n;i++)
      for (j=1;j<=n;j++)
        pos[i][j]=++tmp;
    for (i=1;i<=n;i++)
      for (j=1;j<=n;j++){
        scanf("%d",&w);
        addedge(pos[i][j],pos[i][j]+n*n,1,w);
        if (i        if (j      }   
    S=n*n*2+1; T=S+1;
    addedge(S,1,2,0);
    addedge(n*n*2,T,2,0);
    addedge(1,n*n+1,1,0);
    addedge(n*n,n*n*2,1,0);
}   

void spfa(){
    for (int i=1;i<=T;i++){
        d[i]=-INF;
        v[i]=0;
    }   
    int head=0,tail=1,t;
    list[1]=S; v[S]=1; d[S]=0;
    while (head!=tail){
        head++; if (head>=N) head=0;
        for (t=ls[list[head]];t;t=g[t].next)
          if (g[t].c && d[g[t].x]+g[t].w>d[g[t].y]){
              d[g[t].y]=d[g[t].x]+g[t].w;
              fa[g[t].y]=t;
              if (!v[g[t].y]){
                  v[g[t].y]=1;
                  tail++; if (tail>=N) tail=0;
                  list[tail]=g[t].y;
              }   
          }
        v[list[head]]=0;
    }   
}   

void change(){
    cost+=d[T];
    for (int i=T;i!=S;i=g[fa[i]].x){
      g[fa[i]].c–;
      g[g[fa[i]].op].c++;
    }   
}   

void work(){
    cost=0;
    spfa();
    change();
    spfa();
    change();
}   

int main(){
    while (scanf("%d",&n)!=EOF){
        init();
        work();
        printf("%dn",cost);
    }   
}