题意：有一个矩阵C[i][j]，和一个由01组成的矩阵X[i][j]。X矩阵满足条件：
1.X 12+X 13+…X 1n=1
2.X 1n+X 2n+…X n-1n=1
3.for each i (1 < i < n) , satisfies ∑X ki (1<=k<=n)=∑X ij (1<=j<=n).
现在要求最小的∑C ij*X ij。
思路：好难想的第一次做这种题，根本没有想到最短路上面，也不会建图。
从第一个条件可以看出一号结点出度为1，
从第二个条件可以看出n号节点的入度为1，
从第三个条件可以看出2~n-1号节点的入度必须等于出度。
情况一：直接把C[i][j]看成是一张邻接矩阵，1为起点，n为终点，跑一次最短路，求出最短路sp。
情况二：1号结点有一个非子环的闭环，n号结点有一个非子环的闭环。同时两个闭环存在也满足题意
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <queue>
#include <math.h>
using namespace std;
const int inf=0x3f3f3f3f;
int map[310][310];
int n;
bool vis[310];
int dis[310];
int spfa(int s,int t)
{
for(int i=1;i<=n;++i)
{
dis[i]=inf; vis[i]=0;
}
vis[s]=1; dis[s]=0;
queue<int> que; que.push(s);
while(!que.empty())
{
int u=que.front(); que.pop(); vis[u]=0;
for(int i=1;i<=n;++i)
{
if(dis[i]>dis[u]+map[u][i])
{
dis[i]=dis[u]+map[u][i];
if(!vis[i])
{
vis[i]=1; que.push(i);
}
}
}
}
int ans=inf;
for(int i=1;i<=n;++i)
{
if(i==s) continue;
ans=min(ans,dis[i]+map[i][s]);
}
return ans;
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
for(int i=1;i<=n;++i)
{
for(int j=1;j<=n;++j)
{
scanf("%d",&map[i][j]);
}
}
int r11=spfa(1,n);
int ans=dis[n];
int rnn=spfa(n,1);
printf("%d\n",min(ans,r11+rnn));
}
return 0;
}
