HDU 4370

• 思维题目,将条件转化成最短路来做,观察题目条件.
• 求$\Sigma c_{ij}*x_{ij}$,等价于常数乘以边的权值,恰恰这些常数是只能是0/1,所以只能是边的组合.
• 条件1：起始点1到其余每个点中的任意一个点可以有一条边,出度为1.
• 条件2：其余每一个点中的中任意一个点到终点4(n)可以有一条边,入度为1.
• 条件3：观察下标发现2 - 3之间的点到源点和终点常数都相同,说明2 - n-1之间的点入度和出度相同
• $\Sigma c_{ij}*x_{ij}$,不仅包括了1到n的最短路,还有1到1的环,n到n的环,因为入/出度为1.而中间的点入/出度只要求相同,可以为0.

  #include <iostream>
  #include <string.h>
  #include <queue>
  using namespace std;
  const int maxn = 305;
  int n;
  int e[maxn][maxn];
  bool vis[maxn];
  int dist[maxn];
  
  void spfa(int x,int& ans1) {
  	queue<int> que;
  	memset(dist,0x3f,sizeof dist);
  	memset(vis,0,sizeof vis);
  	dist[x] = 0; vis[x] = 1; que.push(x);
  	while (!que.empty()) {
  		int cur = que.front(); que.pop();
  		vis[cur] = 0;
  		for (int i=1; i<=n; i++) {
  			if (dist[i] > dist[cur] + e[cur][i]) {
  				dist[i] = dist[cur] + e[cur][i];
  				if (!vis[i]) {
  					vis[i] = 1;
  					que.push(i);
  				}
  			}
  			// 更新起始点环的距离
  			if (cur != x) ans1 = min(ans1,dist[cur]+e[cur][x]);
  		}
  	}
  }
  
  int main() {
  //	freopen("a.txt","r",stdin);
  	while (scanf("%d",&n) != EOF) {
  		memset(e,0x3f,sizeof e);
  		for (int i=1; i<=n; i++) 
  			for (int j=1; j<=n; j++) 
  				scanf("%d",&e[i][j]);
  		int ans1=0x3f3f3f3f,ans2=0x3f3f3f3f;
  		spfa(1,ans1); 
  		int ans = dist[n];
  		spfa(n,ans2);
  		cout << min(ans,ans1+ans2) << endl;
  	}
  	return 0;
  }