HDU 4370 - 0 or 1 （SPFA+思维）

题意：给一个N*N的矩阵C，和一个N*N的只由0和1组成的矩阵X。

　　　X满足以下条件：

　　　1.X +X +...X =1 
　　　2.X +X +...X =1 
　　　3.任意 i (1<i<n), 都有 ∑X  (1<=k<=n)=∑X  (1<=j<=n).

求∑C *X (1<=i,j<=n) 的最小值(1<n<=300)。

分析：乍一看也想不到这是道最短路的题。但将模型转换后，则易想到方法。根据01矩阵X满足的条件，可将其转化为一张图，其满足条件为：点1的出度为1；点N的入度为1；任意点v(1<v<n)的入度等于出度。再用矩阵C视作边权，Cij即边 (i，j）的权值，建图。

　　　所求的答案是min（1->N最短路的值，或由点1出发的环加上由点N出发的环的值）。用SPFA分别对点1、点N跑两次最短路。结果即min(d[N],cir[1]+cir[N])。

　

    #include<bits/stdc++.h>

    using namespace std;

    const int INF = 0x3f3f3f3f;

    const int maxn = ;

    struct Spfa{

        int N;

        int G[maxn][maxn];

        int d[maxn];

        bool vis[maxn];

        void init(int N){ this->N=N;}

        void spfa(int s){

            memset(vis,,sizeof(vis));

            queue<int> Q;

            for(int i=;i<=N;++i){

                d[i]=G[s][i];

                if(i!=s){

                    Q.push(i);

                    vis[i]= true;

                }

            }

            d[s]=INF;

            while(!Q.empty()){

                int x =Q.front();Q.pop();

                vis[x] = false;

                for(int i =;i<=N;++i){

                    if(x==i) continue;

                    if(d[i]>d[x]+G[x][i]){

                        d[i]=d[x]+G[x][i];

                        if(!vis[i]){

                            Q.push(i);

                            vis[i]=true;

                        }

                    }

                }

            }

        }

    }G;

    #define LOCAL

    int main()

    {

        #ifdef LOCAL

            freopen("in.txt","r",stdin);

            freopen("out.txt","w",stdout);

        #endif

        int N,M,s,t,u,v,T,tmp;

        while(~scanf("%d",&N)){

            if(!N) break;

            G.init(N);

            for(int i =;i<=N;++i){

                for(int j=;j<=N;++j){

                    scanf("%d",&G.G[i][j]);

                }

            }

            G.spfa();

            int res=G.d[N];

            int cir1=G.d[];

            G.spfa(N);

            int cir2 = G.d[N];

            res=min(res,cir1+cir2);

            printf("%d\n",res);

        }

        return ;

    }