题目链接:HDU4370-0 or 1
题意:
给一个$n×n$的矩阵$A$,要求找到一个符合条件的0-1矩阵$C$,求$min(\Sigma a_{ij}c_{ij)}$。
0-1矩阵C的约束条件:
- $x_{12}+x_{13}+···+x_{1n}=1$
- $x_{1n}+x_{2n}+···+x_{n-1n}=1$
- $\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-n的最短路。
- 有一条从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;
}