AC 留念
不容易啊，这么多年了，第一次又在洛谷上AC了，还是一上来就网络流，也算是没有辜负MIT三个小时的慕课了。
教训在前，以供警示
- 本来用领接数组也就是不求甚解，对于如何快速找到边对应的反向边更是一头雾水，最后还是选择了邻接矩阵结合自己写类迭代器的方法实现；
- 在《算法导论》里简简单单的伪代码我也能深刻理解，甚至出于数学系的使命感把证明也学会了，伪代码大概是这个样子的：
初始化网络流 如果 通过BFS能在网络流中找到一条增广路经 更新增广路线上的流 （直到无法找到一条从Source到Sink的增广路） 根据最大流最小割原理求出整体流的大小很遗憾，在具体实现的过程中没有任何的想法。最后看题解得知可以用BFS储存遍历顺序以供DFS求流时参考的方法；
- 求出来的最大流的大小一直为1，弄得我一头雾水，结果才发现原来是我把DFS的返回值类型设置成了Bool；
- 自己写迭代器的时候出了亿点问题，导致从题目类型层指向Sink迭代的时候一直把下一个迭代对象指向Sink导致死循环；
- 这个算法有点变味了，变成了dinic算法求最大流，方法就是在每次做流的修改的时候就把该次修改最大流的大小加到答案上；
- 日常不看题面，导致漏了一个数据m。
代码删减版
删掉了一些没用的调试和第一版巨丑无比的代码
#include<bits/stdc++.h>
using namespace std;
namespace tokimeki{
// ----------------- 变量
// 题目中的变量
int k,n,m; // 见题目
int t1,t2; // 用作临时输入
// 建网络流所需变量
// 网络流的一层(1 - n) 为题号
// 网络流的二层(PRE - PRE+k) 为类型题数量
int val[2000][2000]; // 用矩阵储存边的flow值
int dep[2000]; // 存BFS用的遍历顺序
// 常量
const int PRE = 1050;
const int SOURCE = 1049;
const int SINK = 1048;
const int MAXN = 1e8;
// ----------------- 处理子函数
// 矩阵存图迭代器
inline int iterFirst(int u){
if(u == SOURCE){ // SOURCE -> 一层
return 1;
}if(u == SINK){ // SINK 为 终点
return -1;
}else if (u < PRE){ // 一层 -> 二层
return PRE + 1;
}else{ // 二层 -> 终点
return SINK;
}
}
inline int iterNext(int u,int i){
if(u == SOURCE){ // SOURCE -> 一层
return i == n ? -1 : i + 1;
}if(u == SINK){ // SINK 为 终点
return -1;
}else if (u < PRE){ // 一层 -> 二层
i ++;
while(i <= PRE + n && !val[u][i]) i ++;
return i > PRE + n ? -1 : i;
}else{ // 二层 -> 终点
return i==SINK ? -1 : SINK;
}
}
// ----------------- 主要过程
// 初始输入及建图
void inputGraph(){
memset(val,0,sizeof(val));
scanf("%d%d",&k,&n);
m = 0;
for(int i=1;i<=k;i++){
scanf("%d",&t1);
val[PRE + i][SINK] = t1;
m += t1;
}
for(int i=1;i<=n;i++){
val[SOURCE][i] = 1;
scanf("%d",&t1);
for(int _t=0;_t<t1;_t++){
scanf("%d",&t2);
val[i][PRE + t2] = 1;
printf("I\t%d -> %d -> %d\n",i,val[i][PRE + t2],PRE + t2);
}
}
}
// BFS求残差网络中是否存在增广路
bool bfs(int root){
int cur; // 当前处理的节点
memset(dep,0,sizeof(dep));
queue<int> q;
q.push(root);
dep[root] = 1;
while(!q.empty()){
cur = q.front(); q.pop();
//cout<<q.size()<<"\t"<<cur<<endl;
//printf("%d\t%d\n",q.size(),cur);
if(cur == SINK){
return true;
}
for(int i=iterFirst(cur);i>0;i=iterNext(cur,i)){
//printf("\t%d\t%d\t%d\n",q.size(),cur,i);
//cout<<"\t"<<q.size()<<"\t"<<cur<<"\t"<<i<<endl;
printf("O\t%d -> %d -> %d\n",cur,val[cur][i],i);
if (!val[cur][i]) continue;
if (dep[i] > 0) continue;
dep[i] = dep[cur] + 1;
q.push(i);
}
}
return false;
}
// DFS求增广路网络流大小并修改
int dfs(int root, int flow){
int remain = flow;
if (root == SINK){
//printf("DFS\t%d\t%d\n",root,flow);
return flow;
}
for(int i=iterFirst(root);i>0;i=iterNext(root,i)){
if (dep[i] != dep[root] + 1) continue;
if (!val[root][i]) continue;
int ret;ret = dfs(i,min(flow,val[root][i]));
if(ret > 0){
val[root][i] -= ret;
val[i][root] += ret;
remain -= ret;
}else{
dep[i] = 0;
}
if (remain <= 0){
break;
}
}
//printf("DFS\t%d\t%d\n",root,flow - remain);
return flow - remain;
}
void printGraph(){
printf("-------------------------\n");
for(int i=iterFirst(SOURCE);i>0;i=iterNext(SOURCE,i)){
printf("\t%d -> %d = %d , %d\n",
SOURCE,i,val[SOURCE][i],val[i][SOURCE]);
}
for(int i=1;i<=n;i++){
for(int j=iterFirst(i);j>0;j=iterNext(i,j)){
printf("\t%d -> %d = %d , %d\n",
i,j,val[i][j],val[j][i]);
}
}
for(int i=PRE+1;i<=PRE+k;i++){
for(int j=iterFirst(i);j>0;j=iterNext(i,j)){
printf("\t%d -> %d = %d , %d\n",
i,j,val[i][j],val[j][i]);
}
}
}
int main(){
//freopen("input.txt","r",stdin);
int ans = 0, res = 0;
inputGraph();
//fclose(stdin);
printGraph();
while(bfs(SOURCE)){
printGraph();
do{
ans += res;
res = dfs(SOURCE,MAXN);
}while(res);
}
if(ans != m){
printf("No Solution!\n");
return 0;
}
for(int u=PRE + 1;u<=PRE + k;u++){
printf("%d: ",u);
for(int v=iterFirst(SOURCE);v>0;v=iterNext(SOURCE,v)){
if(val[u][v] && u!= v){
printf("%d ",v);
}
}
printf("\n");
}
return 0;
}
}
int main(){
tokimeki::main();
return 0;
}
