题面：
Problem Description Given a n*n matrix Cij (1<=i,j<=n),We want to find a n*n matrix Xij (1<=i,j<=n),which is 0 or 1. Besides,Xij meets the following conditions: 1.X12+X13+...X1n=1 2.X1n+X2n+...Xn-1n=1 3.for each i (1<i<n), satisfies ∑Xki (1<=k<=n)=∑Xij (1<=j<=n). For example, if n=4,we can get the following equality: X12+X13+X14=1 X14+X24+X34=1 X12+X22+X32+X42=X21+X22+X23+X24 X13+X23+X33+X43=X31+X32+X33+X34
这道题真的太巧妙了，菜鸡表示顶礼膜拜。
首先我们可以知道：x矩阵每一个位置的1代表就是c矩阵对应位置的那个数选，最后求的就是选出来的这些数的和。
那么这些数怎么选呐？
条件一：第一行必须有且仅有一个1,。
条件二：最后一列必须有且仅有一个1.
对于c矩阵，我们考虑一下一个完全图是不是也是长这个样子的？是的，当然是！！！于是有了非常巧妙的转化，我们如果把c矩阵看成是一个图的话，Cij代表从i到j有一条边权为1的边，那么条件一的意思就是，点1的出度为1，条件二的意思就是点n的入度为1。
接下来我们看条件三：第i行的和等于第i列的和，这个意思就是每一个点的出度等于入度，呐，这样就足够清楚了，1要出去一个点，n要进来一个点，然后其他点的出度等于入度，所以我们求从1到n的最短路就可以了！
然后有一种特殊情况就是，从1出发回到1+从n出发回到n的和<从1到n的最短路，这时候答案就取前面那种情况所以得跑两遍最短路，以1出发一遍，以n出发一遍。
代码：
#include<iostream> #include<cstring> #include<cstdio> #include<queue> using namespace std; const int maxn=310; int n; int a[maxn][maxn]; queue<int>q; bool vis[maxn]; int dis[maxn]; void spfa(int s) { memset(vis,0,sizeof(vis)); memset(dis,127/3,sizeof(dis));//从s出发，dis[s]不是0，而是极大值，因为有 一点值得注意的是，c11和cnn是不能是1的（具体看题面提的条件），所以不能单独成环， 为了出去浪一圈自身还能被更新，就只能设置成极大值了 for(int i=1;i<=n;++i) { if(i==s)continue; dis[i]=a[s][i]; vis[i]=1; q.push(i); } while(!q.empty()) { int k=q.front();q.pop();vis[k]=0; for(int i=1;i<=n;++i) { if(dis[i]>dis[k]+a[k][i]) { dis[i]=dis[k]+a[k][i]; if(!vis[i]) { q.push(i);vis[i]=1; } } } } } int main() { while(scanf("%d",&n)!=EOF) { for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) { scanf("%d",&a[i][j]); } spfa(1); int c1=dis[1],ans=dis[n]; spfa(n); int c2=dis[n]; if(ans>c1+c2)ans=c1+c2; printf("%d ",ans); } return 0; }