0 or 1
题目链接：
Rhttp://acm.hust.edu.cn/vjudge/contest/122685#problem/R
Description
``` Given a n*n matrix C ij (1<=i,j<=n),We want to find a n*n matrix X ij (1<=i,j<=n),which is 0 or 1.Besides,X ij meets the following conditions:
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).
For example, if n=4,we can get the following equality:
X 12+X 13+X 14=1
X 14+X 24+X 34=1
X 12+X 22+X 32+X 42=X 21+X 22+X 23+X 24
X 13+X 23+X 33+X 43=X 31+X 32+X 33+X 34
Now ,we want to know the minimum of ∑C ij*X ij(1<=i,j<=n) you can get.
Hint
For sample, X 12=X 24=1,all other X ij is 0.
</big>
##Input
<big>
The input consists of multiple test cases (less than 35 case).
For each test case ,the first line contains one integer n (1<n<=300).
The next n lines, for each lines, each of which contains n integers, illustrating the matrix C, The j-th integer on i-th line is C ij(0<=C ij<=100000).
</big>
##Output
<big>
For each case, output the minimum of ∑C ij*X ij you can get.
</big>
##Sample Input
<big>
4
1 2 4 10
2 0 1 1
2 2 0 5
6 3 1 2
</big>
##Sample Output
<big>
3
</big>
##Hint
<big>
</big>
<br/>
##题意：
<big>
求满足题目条件的最小和.
</big>
<br/>
##题解：
<big>
一道多校的好题，一开始还是以为是个dp什么的，看了题解才知道居然可以用图论做.
题目的条件分别表示：起点出度为1，终点入度为1，其他点出入度相等.
这就描述了从起点到终点的一条简单路径. 即求最短路.
考虑特殊情况还需要记录起点和终点的最小环(非自环).
<br/>
详细题解参考下面的第二份代码.
</big>
<br/>
##代码：
``` cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <vector>
#define LL long long
#define eps 1e-8
#define maxn 310
#define mod 1000000007
#define inf 0x3f3f3f3f
#define IN freopen("in.txt","r",stdin);
using namespace std;
int n;
int value[maxn][maxn];
int dis[maxn];
int pre[maxn];
bool vis[maxn];
int dijkstra(int s) {
int cir = inf; // 最小花费环(经过s)
memset(vis, 0, sizeof(vis));
memset(pre, -1, sizeof(pre));
for(int i=1; i<=n; i++) dis[i] = inf; dis[s] = 0;
for(int i=1; i<=n; i++) {
int p, mindis = inf;
for(int j=1; j<=n; j++) {
if(!vis[j] && dis[j]<mindis)
mindis = dis[p=j];
}
vis[p] = 1;
for(int j=1; j<=n; j++) {
if(j==s && p!=s) //不能是自环
cir = min(cir, dis[p]+value[p][s]);
if(dis[j] > dis[p]+value[p][j]) {
dis[j] = dis[p] + value[p][j];
pre[j] = p;
}
}
}
return cir;
}
int main(void)
{
//IN;
while(scanf("%d", &n) != EOF && n)
{
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++) {
int x; scanf("%d", &x);
value[i][j] = x;
}
int cir1 = dijkstra(n);
int cir2 = dijkstra(1);
int ans = min(dis[n], cir1+cir2);
printf("%d
", ans);
}
return 0;
}
参考题解及代码：
/*
HDU 4370 0 or 1
转换思维的题啊，由一道让人不知如何下手的题，转换为了最短路
基本思路就是把矩阵看做一个图，图中有n个点，1号点出度为1，
n号点入度为1，其它点出度和入度相等，路径长度都是非负数，
等价于一条从1号节点到n号节点的路径，故Xij=1表示需要经
过边(i,j)，代价为Cij。Xij=0表示不经过边(i,j)。注意到Cij非负
且题目要求总代价最小，因此最优答案的路径一定可以对应一条简单路径。
最终，我们直接读入边权的邻接矩阵，跑一次1到n的最短路即可，记最短路为path。
漏了如下的情况B：
从1出发，走一个环（至少经过1个点，即不能
是自环），回到1；从n出发，走一个环（同理），回到n。
也就是1和n点的出度和入度都为1，其它点的出度和入度为0.
由于边权非负，于是两个环对应着两个简单环。
因此我们可以从1出发，找一个最小花费环，记代价为c1,
再从n出发，找一个最小花费环，记代价为c2。
（只需在最短路算法更新权值时多加一条记录即可：if(i==S) cir=min(cir,dis[u]+g[u][i])）
故最终答案为min(path,c1+c2)
*/
/*
本程序用SPFA来完成最短路。
但是由于要计算从出发点出发的闭环的路径长度。
所以要在普通SPFA的基础上做点变化。
就是把dist[start]设为INF。同时一开始并不是让出发点入队，而是让
出发点能够到达的点入队。
*/
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
const int INF=0x3f3f3f3f;
const int MAXN=330;
int cost[MAXN][MAXN];//保存路径长度的邻接矩阵
int dist[MAXN];
int que[MAXN];//注意队列的循环利用，建成循环队列
bool vis[MAXN];//是否在队列中标记
void SPFA(int start,int n)
{
int front=0,rear=0;
for(int v=1;v<=n;v++)//初始化
{
if(v==start)//由于要找start的闭环，所以dist[start]设为INF，且不入队
{
dist[v]=INF;
vis[v]=false;
}
else if(cost[start][v]!=INF)
{
dist[v]=cost[start][v];
que[rear++]=v;
vis[v]=true;
}
else//即dist[start][v]==INF情况，对本题没有这种情况
{
dist[v]=INF;
vis[v]=false;
}
}
while(front!=rear)//注意这个条件是不等，因为是循环队列
{
int u=que[front++];
for(int v=1;v<=n;v++)
{
if(dist[v]>dist[u]+cost[u][v])
{
dist[v]=dist[u]+cost[u][v];
if(!vis[v])//不在队列
{
vis[v]=true;
que[rear++]=v;
if(rear>=MAXN) rear=0;//循环队列
}
}
}
vis[u]=false;
if(front>=MAXN)front=0;
}
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int n;
while(scanf("%d",&n)!=EOF)
{
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&cost[i][j]);
SPFA(1,n);
int ans=dist[n];//1到n的最短路
int loop1=dist[1];//1的闭环长度
SPFA(n,n);
int loopn=dist[n];//n的闭环长度
ans=min(ans,loop1+loopn);
printf("%d
",ans);
}
return 0;
}