题目链接：HDU4370-0 or 1

题意：

给一个$n×n$的矩阵$A$，要求找到一个符合条件的0-1矩阵$C$,求$min(\Sigma a_{ij}c_{ij)}$。

0-1矩阵C的约束条件：

1. $x_{12}+x_{13}+···+x_{1n}=1$
2. $x_{1n}+x_{2n}+···+x_{n-1n}=1$
3. $\Sigma x_{ki}=\Sigma x_{ij},1<i<n,1\leq j,k\leq n$

题解：

一个超级神奇的建图。

先考虑模型转化，$c_{ij}$为1时表示走过这条边，为0时表示没走这条边。

然后就可以开始建图了。

我们可以把$C$中的行理解为图的出度，列理解为入度。

对于约束条件1和2，可以转化为1号点的出度为1，n号点的入度为1。

对于约束条件3，可以转化为2-n-1号点的出入度相等。

然后考虑问题的解，有两种情况：

1. 有一条1-n的最短路。
2. 有一条从1出发回到1的最小环，有一条从n出发回到n的最小环。

比较二者大小即可。

对于第二种情况，因为要求从1出发至少过1个点的最小环，所以在初始化时不能把1号点加入堆中。

参考代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 0x3f3f3f3f3f3f3f3f;
int n;
int a[309][309];
struct node
{
    int u;
    ll d;
    node(int u, ll d) : u(u), d(d) {}
    bool operator<(const node &a) const
    {
        return d > a.d;
    }
};
bool used[309];
ll dis[309];
void dijkstra(int st)
{
    priority_queue<node> que;
    while (!que.empty())
        que.pop();
    memset(dis, inf, sizeof(dis));
    for(int i=1;i<=n;i++)
    {
        if(i==st)
            continue;
        int v=i;
        ll w=a[st][i];
        que.push({v,dis[v]=w});
    }
    memset(used, 0, sizeof(used));
    while (!que.empty())
    {
        int u = que.top().u;
        que.pop();
        if (used[u])
            continue;
        used[u] = 1;
        for (int i = 1; i <= n; i++)
        {
            int v = i;
            ll w = a[u][i];
            if (used[v])
                continue;
            if (dis[v] > dis[u] + w)
            {
                dis[v] = dis[u] + w;
                que.push(node(v, dis[v]));
            }
        }
    }
}
int main()
{
    while (scanf("%d", &n) == 1)
    {
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                scanf("%d", &a[i][j]);
        dijkstra(1);
        ll ans = dis[n], p1 = dis[1];
        dijkstra(n);
        ll p2 = dis[n];
        printf("%lld\n", min(ans, p1 + p2));
    }
    return 0;
}