HDU 4370 0 or 1(The shortest path)

Description

给出一个方形矩阵，求构造一个同样大小的（只含0、1）方形矩阵，在满足三个条件的前提下，两矩阵相同位置上的数字乘积总和最小。

Analyze

这题的建模思想绝了！谁能想到乍一看这么像数论的题目其实是个图论题！

将方形矩阵视为n个点的图，位置(i, j)上权值代表从 i 到 j 的距离

第一个条件规定点1有且仅有一个出度

第二个条件规定点n有且仅有一个入度

第三个条件规定其他点 入度 == 出度

有符合以上条件的两种模型

第一种模型：根据所求可转化为求最短路（首先能成一棵树，来满足‘度’的限制，然后代价最小。因为有方向所以是最短路，否则我想最小生成树可能也可…）

第二种模型是1、n两个非自环之最小环之和

在 分别以他们为起点，求最短路的过程中 可以求出

Code

#include <queue>
#include <stack>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;

int n, path, circle, t_circle;
int e[305][305], dis[305], vis[305];

void Dijkstra(int start)
{
    memset(vis, 0, sizeof(vis));
    memset(dis, INF, sizeof(dis));
    dis[start] = 0;
    int mmin = INF, pos = -1;
    for(int i = 1; i <= n; ++i)
    {
        mmin = INF, pos = -1;
        for(int j = 1; j <= n; ++j)
            if(!vis[j] && dis[j] < mmin)
                mmin = dis[j], pos = j;
        vis[pos] = 1;
        for(int j = 1; j <= n; ++j)
        {
            dis[j] = min(dis[j], dis[pos] + e[pos][j]);
            if(j == start && pos != start)
                circle = min(circle, dis[pos] + e[pos][j]);
        }
    }
}


int main()
{
    while(~scanf("%d", &n))
    {
        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= n; ++j)
                scanf("%d", &e[i][j]);

        circle = INF;
        Dijkstra(1);
        path = dis[n];

        t_circle = circle;

        circle = INF;
        Dijkstra(n);

        cout << min(path, t_circle + circle) << '\n';
    }
    return 0;
}