原题链接:http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2304

题意:

给你一个网络,其中每条边的容量是1,你可以通过调整边的方向来获得更大的流量,现在问你能获得的最大流量是多少。并且输出更改方向的边的编号。

题解:

就每条边弄成无向的,并且标记一下是否是原始边,然后跑一发Dinic即可。然后在残余网络上寻找解即可。

代码:

#include<iostream>
#include<stack>
#include<vector>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<queue>
#define MAX_S (1<<10)+10
#define MAX_V 500
#define MAX_N MAX_V
#define INF 1000009
using namespace std; struct edge {
int to, cap, rev;
bool isRev;
bool isOri;
int id; edge(int t, int c, int r, bool ir, bool io,int iid)
: to(t), cap(c), rev(r), isRev(ir), isOri(io),id(iid) { } edge() { }
}; template <class T>
inline bool scan_d(T &ret)
{
char c;
int sgn;
if(c=getchar(),c==EOF) return ; //EOF
while(c!=' -' &&(c<'' ||c>'' )) c=getchar();
sgn=(c==' -' )?-:;
ret=(c==' -' )?:(c-'' );
while(c=getchar(),c>='' &&c<='' ) ret=ret*+(c-'' );
ret*=sgn;
return ;
} vector<edge> G[MAX_N];
int level[MAX_V];
int iter[MAX_V]; void init(int totNode) {
for (int i = ; i <= totNode; i++)
G[i].clear();
memset(level, , sizeof(level));
memset(iter, , sizeof(iter));
} void add_edge(int from,int to,int cap,bool io,int id) {
G[from].push_back(edge (to, cap, G[to].size(),,io,id));
G[to].push_back(edge (from, , G[from].size() - ,,io,id));
} void bfs(int s) {
queue<int> que;
memset(level, -, sizeof(level));
level[s] = ;
que.push(s);
while (!que.empty()) {
int v = que.front();
que.pop();
for (int i = ; i < G[v].size(); i++) {
edge &e = G[v][i];
if (e.cap > && level[e.to] < ) {
level[e.to] = level[v] + ;
que.push(e.to);
}
}
}
} int dfs(int v,int t,int f) {
if (v == t)return f;
for (int &i = iter[v]; i < G[v].size(); i++) {
edge &e = G[v][i];
if (e.cap > && level[v] < level[e.to]) {
int d = dfs(e.to, t, min(f, e.cap));
if (d > ) {
e.cap -= d;
G[e.to][e.rev].cap += d;
return d;
}
}
}
return ;
} int max_flow(int s,int t) {
int flow = ;
for (; ;) {
bfs(s);
if (level[t] < )return flow;
memset(iter, , sizeof(iter));
int f;
while ((f = dfs(s, t, INF)) > ) {
flow += f;
}
}
} int S,T; int N,M; vector<int> ans; int main() {
scanf("%d%d", &N, &M);
for (int i = ; i < M; i++) {
int u, v;
scanf("%d%d", &u, &v);
add_edge(u, v, , , i + );
add_edge(v, u, , , i + );
}
scanf("%d%d", &S, &T);
int f = max_flow(S, T);
printf("%d\n", f);
for (int i = ; i <= N; i++)
for (int j = ; j < G[i].size(); j++)
if (G[i][j].isRev == && G[i][j].isOri == && G[i][j].cap == )
ans.push_back(G[i][j].id);
printf("%d\n", ans.size());
for (int i = ; i < ans.size(); i++)
printf("%d\n", ans[i]);
return ;
}

最新文章

  1. 雾里看花般的迷茫--货运APP
  2. 存储过程之七—java代码调用
  3. JBoss错误
  4. (三)----使用HttpClient发送HTTP请求(分别通过GET和POST方法发送数据)
  5. ffmpeg常用命令---转
  6. 【Unity3D与23种设计模式】中介者模式(Mediator)
  7. python实现可以被with上下文管理的类或函数
  8. day-09内存管理
  9. .net core 存储base64的图片或文件
  10. 第四百一十六节,Tensorflow简介与安装
  11. PTA 7-1 畅通工程之局部最小花费问题(35 分)
  12. 网站钓鱼的方法 和 xss
  13. [学习笔记]K-D Tree
  14. java JNative调用DLL中带引用类型的方法
  15. FFmpeg编译:jni not found 的问题
  16. mysql中varbinary、binary、char、varchar异同
  17. ANT发送邮件需要的3个JAR包
  18. Windows WaveIn 录音
  19. Django的views视图系统
  20. Hive中的数据倾斜

热门文章

  1. 重写BaseAdapter实现ListView
  2. Diycode开源项目 Glide图片加载分析
  3. MySQL时间字段究竟使用INT还是DateTime
  4. 数据库路由中间件MyCat - 源代码篇(10)
  5. IOS开发学习笔记027-UITableView 使用模型对象
  6. MongoDB快速入门学习笔记1 windows安装MongoDB
  7. Python-S9-Day126——Scrapy爬虫框架
  8. C# 反射修改私有静态成员变量
  9. angular2多组件通信流程图
  10. POJ 2217:Secretary(后缀数组)