hdu43700 or 1【01规划模型 最短路】

4
1 2 4 10
2 0 1 1
2 2 0 5
6 3 1 2  

3  

题意： （先说直接翻译过来的）

给出nxn矩阵Ci,j 求01矩阵Xij满足

1.X ₁₂+X ₁₃+...X _1n=1
2.X _1n+X _2n+...X _n-1n=1
3.X矩阵的第i行的和等于第i列的和

做法&思路：

是在最短路分类里的QAQ百思不得其解，先把示例画出来。

咦？有行有列，莫非是拆点了？对于示例选的边可以画出这个图：

好像X矩阵是用来控制C矩阵加边与否的耶

再编一组数据找找规律

看着怎么这么眼熟，我是不是可以从右边往左边加边啊

另一个图：

越想越觉得有道理啊，因为要求第i行和第i列的和相等，就相当于通过新加的边过渡行与列，拆点，连边，其他的边正常连接就好，交了 WA了

看讨论区 有这样一组示例 ，连接的是中间图，咦？怎么分开了，所以我们需要连一个6->5的边

这样就存在两个问题：

1.有可能1->6->5->10,怎么办？1->6 5->10赋成无穷大，不走它就得了

2.如果分成好多团怎么办？依旧只连6->5，因为中间那部分就相当于for each i (1<i<n), satisfies ∑X _ki (1<=k<=n)=∑X _ij (1<=j<=n)=0了

    #include<iostream>
    #include<cstring>
    #include<cstdlib>
    #include<queue>
    #include<cstdio>
    using namespace std;
    int n,m,x;
    const long long  MAXINT=0x3f3f3f3f;
    const int MAXNUM=609;
    long long dist[MAXNUM];
    long long A[MAXNUM][MAXNUM];
    void Dijkstra(int v0)
    {
        bool S[MAXNUM];// 判断是否已存入该点到S集合中
        for(int i=1; i<=n; ++i)
        {
            dist[i]=A[v0][i];
           // printf("%d    ",dist[i]);
            S[i]=false; // 初始都未用过该点
        }
       // dist[v0] = 0;
        S[v0]=true;
        for(int i=2; i<=n; i++)
        {
            long long mindist = MAXINT;
            int u = -1;// 找出当前未使用的点j的dist[j]最小值
            for(int j=1; j<=n; ++j)
            if((!S[j]) && dist[j]<mindist)
            {
                u = j;// u保存当前邻接点中距离最小的点的号码
                mindist = dist[j];
                //printf("%d        ",mindist);
            }
            S[u] = true;
            for(int j=1; j<=n; j++)
                if((!S[j]) && A[u][j]<MAXINT)
                {
                    if(dist[u] + A[u][j] < dist[j])     //在通过新加入的u点路径找到离v0点更短的路径
                    {
                        dist[j] = dist[u] + A[u][j];    //更新dis                    //记录前驱顶点
                    }
                }
        }
        return;
    }
    int main()
    {
       //freopen("in.txt","r",stdin);
        while(~scanf("%d",&n))
        {
            for(int i=1; i<=n*2; i++)
            {
                for(int j=1; j<=n*2; j++)
                    if(i-j==n) A[i][j]=0;
                    else A[i][j]=MAXINT;
            }
            for(int i=1;i<=n;i++)
                for(int j=1+n;j<=n*2;j++)
                    scanf("%I64d",&A[i][j]);
            A[1][n+1]=A[n][n+n]=MAXINT;
            A[n+1][n]=0;
           // A[1][1+n]=A[n][n*2]=MAXINT;
          //  for(int i=1;i<=2*n;i++)for(int j=1;j<=2*n;j++)printf("i=%d,j=%d,A=%d\n",i,j,A[i][j]);
            n=n+n;
            Dijkstra(1);
            //for(int i=n/2+1;i<=n;i++)
            printf("%I64d\n",dist[n]);
        }
        return 0;
    }