(中等) HDU 4370 0 or 1，建模+Dijkstra。-白红宇

(中等) HDU 4370 0 or 1，建模+Dijkstra。

阅读量：5012 次

发布时间：2019-06-12

本文共 1744 字，大约阅读时间需要 5 分钟。

　　Description

　　Given a n*n matrix C _ij (1<=i,j<=n),We want to find a n*n matrix X _ij (1<=i,j<=n),which is 0 or 1.

　　Besides,X _ij meets the following conditions:

1.X ₁₂+X ₁₃+...X _1n=1

2.X _1n+X _2n+...X _n-1n=1

3.for each i (1<i<n), satisfies ∑X _ki (1<=k<=n)=∑X _ij (1<=j<=n).

　　For example, if n=4,we can get the following equality:

X ₁₂+X ₁₃+X ₁₄=1

X ₁₄+X ₂₄+X ₃₄=1

X ₁₂+X ₂₂+X ₃₂+X ₄₂=X ₂₁+X ₂₂+X ₂₃+X ₂₄

X ₁₃+X ₂₃+X ₃₃+X ₄₃=X ₃₁+X ₃₂+X ₃₃+X ₃₄

　　Now ,we want to know the minimum of ∑C _ij*X _ij(1<=i,j<=n) you can get.

　　神题，可以转化为最短路问题。这个题可以一点一点的分析，首先就是选了第一行的第k个之后，就要选一个第k行的，所以建边 1->k 边权为第一行第k个的值，然后求1->n的最短路就好。。。。。。

　　不过这里还有一种特殊情况，就是1和其他形成一个环，N和其他形成一个环。所以答案就是两个环的和，和最短路中小的那一个。。。

代码如下：

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                   using namespace std;const int MaxN=400;const int INF=10e8;void Dijkstra(int cost[][MaxN],int lowcost[],int N,int start){ priority_queue 
                  
                    que; int t; for(int i=1;i<=N;++i) lowcost[i]=INF; que.push(start); while(!que.empty()) { t=que.top(); que.pop(); for(int i=1;i<=N;++i) if(i!=t) if(lowcost[t]==INF || lowcost[i]>lowcost[t]+cost[t][i]) { lowcost[i]=(lowcost[t]==INF ? 0 : lowcost[t])+cost[t][i]; que.push(i); } }}int map1[MaxN][MaxN];int ans[MaxN];int main(){ //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); int N; int t1,t2; while(~scanf("%d",&N)) { for(int i=1;i<=N;++i) for(int j=1;j<=N;++j) scanf("%d",&map1[i][j]); Dijkstra(map1,ans,N,1); t1=ans[N]; t2=ans[1]; Dijkstra(map1,ans,N,N); t2+=ans[N]; printf("%d\n",min(t1,t2)); } return 0;}

View Code

转载于:https://www.cnblogs.com/whywhy/p/4337893.html

你可能感兴趣的文章