- 题意：大意就是在一个图中给定条件让寻找欧拉回路，使得欧拉回路最短，不过这个欧拉回路有些特殊，有些边可以多次经过，有些边则可以不经过。
- 分析：给出四种类型 ，不难看出，a,b类型是必须有的，只是边的经过次数多少，在最终的图中，凡是经过多次的我都添加了多条边，而对于c d则是可选择的，怎么样让可选择的路径最短呢，可以使用最小费用最大流
s,t为起始和终点，注意到要选择cd使得能构成欧拉回路(已知连通)，仅需入度等于出度即可，所以对于每个点进行统计 出度-入度,用a,c,d来补偿原图中缺少的度数，对应a,c的容量是无限的，d则是1，费用都为1，然后继续构建用于求最小费用最大流的图,s到每一个出度小于入度的点有边,t到每个出度大于入度的点有边值为入度减出度， a,c,d的边都是出-入，表示补偿。 求出最大流并且得等于diff之和，说明补偿完全
接着按照上面图每个边的流量和原图中的a,c组合成新图，其存在欧拉回路
最后DFS遍历图，计数即可。
还是太菜了,WA了，不想改了。。。
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#include<iostream>
#include<vector>
//#define test
using namespace std;
/*
需要清理 可重复经过
A 1 1 纳入可拓展出边的范围 但是保证至少有一个
B 1 0
c 0 1 纳入可拓展出边的范围 即多重边
d 0 0
*/
const int INF = 1000000000;
typedef long long ll;
struct Edge {
int from, to, cap, flow,cost;
Edge(int u, int v, int c, int f,int w):from(u),to(v),cap(c),flow(f),cost(w) {}
};
const int maxn = 100+10;
//最小费用流
struct MCMF{//最小费用最大流
// int n , m;
vector<Edge>edges; //保存各边
vector<int> G[maxn]; //存储各点的所有邻边序号
int inq[maxn]; //是否在队列中
int d[maxn]; //bellman最短路径
int p[maxn]; //上一条弧，方便进行打印
int a[maxn]; //可以改进量
void init(int n){
for(int i = 0; i < n; i++){
G[i].clear();
}
edges.clear();
}
void AddEdge(int from, int to, int cap, int cost){
edges.push_back(Edge(from,to,cap,0,cost));
edges.push_back(Edge(to,from,0,0,-cost)); //不懂为什么要加反向边
int m=edges.size();
G[from].push_back(m-2);
G[to].push_back(m-1);//记录边序号
}
bool bellman(int s, int t,int & flow, long long &cost){
for(int i = 0; i < maxn; i++) d[i]= INF;
memset(inq,0,sizeof(inq));
d[s] = 0, inq[s] = 1; a[s] = INF;
queue<int> Q;
Q.push(s);//入队
while(!Q.empty()){
int u = Q.front(); Q.pop();
inq[u] = 0;
for(int i = 0; i <(int) G[u].size(); i++){
Edge& e = edges[G[u][i]];
if(e.cap > e.flow && d[e.to] > d[u] + e.cost){ //cap大并且边可以拓展
d[e.to] = d[u] + e.cost;
p[e.to] = G[u][i];
a[e.to] = min(a[u],e.cap - e.flow);//可拓展最小
if(!inq[e.to]){
Q.push(e.to);
inq[e.to] = 1;
}
}
}
}
if(d[t] == INF) return false;//如果仍然没到达，说明不可达
flow += a[t];
cost +=(ll)d[t] * (ll)a[t];//总体积
for(int u =t; u!=s; u=edges[p[u]].from){
edges[p[u]].flow += a[t];
edges[p[u]^1].flow -= a[t];//另一方向要减
}
return true;
}
//保证初始网络中没有负权圈
int MincostMaxflow(int s, int t, long long& cost){
int flow =0; cost = 0;
while(bellman(s,t,flow,cost));
return flow;
}
};
MCMF g;
const int maxm = 500 + 5;
int n, m, u[maxm], v[maxm], type[maxm], id[maxm], diff[maxn],ext[maxn];
int T,S;//数据组数 ，测试点编号，
double E = 0;//每条管道消耗包子数
// for euler tour only
vector<int> G[maxn];
vector<int> vis[maxn];
vector<int> path;
void clear(){
memset(u,0,sizeof(u));
memset(v,0,sizeof(u));
memset(type,0,sizeof(u));
memset(id,0,sizeof(u));
memset(diff,0,sizeof(u));
for(int i =0; i < maxn; i ++) {
vis[i].clear();
G[i].clear();
}
path.clear();
n = 0, m= 0;
MCMF g1;
g = g1;
}
void euler(int u) {
for(int i = 0; i <(int) G[u].size(); i++)
if(vis[u][i]<=0) {
vis[u][i]++;
euler(G[u][i]);
path.push_back(G[u][i]+1);
}
}
void print_answer() {
// build the new graph
for(int i = 0; i < n; i++) { G[i].clear(); vis[i].clear(); }
for(int i = 0; i < m; i++) {//对ABC类型进行边的生成 具体来说就是如果可以多次经过就生成多个边
switch(type[i]){
case 1:
for(int j = 0 ; j < g.edges[id[i]].flow+1; j++){
G[u[i]].push_back(v[i]);//在欧拉回路中记录的边
}
vis[v[i]].push_back(0);
break;
case 2:
G[u[i]].push_back(v[i]);
vis[v[i]].push_back(0);
break;
case 3:
for(int j = 0 ; j < g.edges[id[i]].flow; j++){
G[u[i]].push_back(v[i]);//因为原来默认C类型是没有的
}
vis[v[i]].push_back(0);
break;
case 4:
if(g.edges[id[i]].flow)//最多加一个并且有条件
G[u[i]].push_back(v[i]);//因为原来默认D类型是没有的
vis[v[i]].push_back(0);
break;
}
}
// print euler tour
path.clear(); //每次清理掉之前的路径
euler(0);
int ans = path.size();
cout << (ans*E)<<endl;
// printf("\n");
}
int main() {
cin >> T >> S >> E;
while(T--) {
clear();
scanf("%d%d", &n, &m);//
g.init(n+2); //n+2 points within s and t
memset(diff, 0, sizeof(diff));
for(int i = 0; i < m; i++) {
char dir[9];
scanf("%d%d%s", &u[i], &v[i], dir);
type[i] = dir[0] - 'A' +1;
switch(type[i]){
case 1: //1 1
u[i]--; v[i]--;//从0开始
diff[u[i]]++; diff[v[i]]--;
id[i] = g.edges.size(); g.AddEdge(u[i],v[i],10000,1);//加入最大流的是除了A外额外的边
break;
case 2:// 1 0
u[i]--; v[i]--;
diff[u[i]]++; diff[v[i]]--; //给图上加点
break;
case 3:// 0 1
u[i]--; v[i]--;
id[i] = g.edges.size(); g.AddEdge(u[i],v[i],10000,1);//加入最大流边 可扩大10000
break;
case 4://0 0 //最多只有一条边
u[i]--; v[i]--;
id[i] = g.edges.size(); g.AddEdge(u[i],v[i],1,1);
break;
}
}
bool ok = true;
int s = n, t = n+1;
if(ok) {
int sum = 0;
for(int i = 0; i < n; i++) {
if(diff[i] < 0) { g.AddEdge(s, i, -1*diff[i],0); sum -= diff[i]; } // provide "out-degree" 表示出度减入度缺少的数，用入度减出度多余的边来填充
if(diff[i] > 0) { g.AddEdge(i, t, diff[i],0); sum += diff[i];}
}
ll ans;
int flow = g.MincostMaxflow(s, t,ans);
if( flow != sum) ok = false;
}
if(!ok) printf("-1\n");
else print_answer(); // underlying graph is always connected
/*打印点邻边*/
// for(int i = 0; i < n; i++) {
// cout <<"点"<<i+1<<":";
// for(auto j:G[i] ){
// cout << j+1<<" ";
// }
// cout <<endl;
// }
// if(T) printf("\n");
}
return 0;
}
网友评论