题意：
在一个(100*100)的方格中，要求从(b)走到(g)，途中经过(c)但不经过(u)，并且不能走已经做过的路。如果可以，就求出路径。
思路：
拆点建费用流，看能不能从(c)走两条路走到(b，g)。然后输出路径。
代码：
#include<set>
#include<map>
#include<cmath>
#include<queue>
#include<bitset>
#include<string>
#include<cstdio>
#include<vector>
#include<cstring>
#include <iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 20000 + 5;
const int M = 50 + 5;
const ull seed = 131;
const int INF = 0x3f3f3f3f;
const ll MOD = 1000000007;
struct Edge{
int to, next, cap, cost;
}edge[10000 * 4 * 10 + 100];
int head[maxn], tot;
int pre[maxn], dis[maxn];
bool vis[maxn];
int N;
void init(){
N = maxn;
tot = 0;
memset(head, -1, sizeof(head));
}
void addEdge(int u, int v, int cap, int cost){ //双向边
edge[tot].to = v;
edge[tot].cap = cap;
edge[tot].cost = cost;
edge[tot].next = head[u];
head[u] = tot++;
edge[tot].to = u;
edge[tot].cap = 0;
edge[tot].cost = -cost;
edge[tot].next = head[v];
head[v] = tot++;
}
bool spfa(int s, int t){
queue<int> q;
for(int i = 0; i <= N; i++){
dis[i] = INF;
vis[i] = false;
pre[i] = -1;
}
dis[s] = 0;
vis[s] = true;
q.push(s);
while(!q.empty()){
int u = q.front();
q.pop();
vis[u] = false;
for(int i = head[u];i != -1;i = edge[i].next){
int v = edge[i].to;
int c = edge[i].cap;
int w = edge[i].cost;
if(c && dis[v] > dis[u] + w){
dis[v] = dis[u] + w;
pre[v] = i;
if(!vis[v]){
vis[v] = true;
q.push(v);
}
}
}
}
return pre[t] != -1;
}
int MCMF(int s, int t, int &cost){
int flow = 0;
cost = 0;
while(spfa(s, t)){
int MIN = INF;
for(int i = pre[t]; i != -1;i = pre[edge[i ^ 1].to]){
MIN = min(MIN, edge[i].cap);
}
for(int i = pre[t]; i != -1; i = pre[edge[i ^ 1]. to]){
edge[i]. cap -= MIN;
edge[i ^ 1]. cap += MIN;
cost += edge[i]. cost * MIN;
}
flow += MIN;
}
return flow;
}
int n, m ,bx, by, cx, cy, gx, gy, ux, uy;
int getid(int x, int y, int out){
return (x - 1) * m + y + n * m * out;
}
char getturn(int a, int b){
int x1 = (a - 1) / m + 1, x2 = (b - 1) / m + 1;
int y1 = a - (x1 - 1) * m, y2 = b - (x2 - 1) * m;
if(x1 + 1 == x2) return 'U';
if(x1 - 1 == x2) return 'D';
if(y1 + 1 == y2) return 'R';
if(y1 - 1 == y2) return 'L';
}
/***********************/
输出路径
string step;
int ans[20000], cnt;
vector<int> g[maxn];
void dfs(int s, int t){
vis[s] = 1;
if(s == t) return;
for(int i = 0; i < g[s].size(); i++){
int v = g[s][i];
if(!vis[v]){
vis[v] = 1;
ans[cnt++] = v;
dfs(v, t);
break;
}
}
}
void path(int st, int en){
for(int i = 1; i <= n * m; i++){
g[i].clear();
for(int j = head[i + n * m]; j != -1; j = edge[j].next){
int c = edge[j].cap;
int v = edge[j].to;
if(!c && i != v){ //流量为0
g[i].push_back(v);
}
}
}
string tmp;
memset(vis, 0, sizeof(vis));
step = "";
cnt = 0;
ans[cnt++] = getid(cx, cy, 0);
dfs(st, en), cnt--;
tmp = "";
if(ans[cnt - 1] == getid(gx, gy, 0)){
tmp = "";
for(int i = 0; i < cnt - 1; i++){
tmp += getturn(ans[i], ans[i + 1]);
}
step = step + tmp;
}
else{
tmp = "";
for(int i = cnt - 1; i > 0; i--){
tmp += getturn(ans[i], ans[i - 1]);
}
step = tmp + step;
}
cnt = 0;
ans[cnt++] = getid(cx, cy, 0);
dfs(st, en), cnt;
tmp = "";
if(ans[cnt - 1] == getid(gx, gy, 0)){
tmp = "";
for(int i = 0; i < cnt - 1; i++){
tmp += getturn(ans[i], ans[i + 1]);
}
step = step + tmp;
}
else{
tmp = "";
for(int i = cnt - 1; i > 0; i--){
tmp += getturn(ans[i], ans[i - 1]);
}
step = tmp + step;
}
}
/***********************/
int main(){
int cost;
int to[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
while(scanf("%d%d", &n, &m) && n + m){
init();
scanf("%d%d", &bx, &by);
scanf("%d%d", &cx, &cy);
scanf("%d%d", &gx, &gy);
scanf("%d%d", &ux, &uy);
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
int x, y;
addEdge(getid(i, j, 0), getid(i, j, 1), 1, 1);
addEdge(getid(i, j, 1), getid(i, j, 0), 1, 1);
for(int k = 0; k < 4; k++){
x = i + to[k][0];
y = j + to[k][1];
if(x < 1 || y < 1 || x > n || y > m) continue;
if((x == ux && y == uy) || (i == ux && j == uy)) continue;
addEdge(getid(i, j, 1), getid(x, y, 0), 1, 1);
}
}
}
int st = getid(cx, cy, 1), en = 2 * n * m + 1;
addEdge(getid(bx, by, 1), en, 1, 1);
addEdge(getid(gx, gy, 1), en, 1, 1);
int flow = MCMF(st, en, cost);
if(flow < 2) printf("NO
");
else{
path(getid(cx, cy, 0), en);
printf("YES
");
cout << step << endl;
}
}
return 0;
}