https://www.luogu.com.cn/problem/P2936
本题相比普通最大流题目只是多了一个重边的处理,意义不大,但还是想记录一下,反正也花不了多少时间。
这里的处理方式是使用二维数组预处理边集,将重边合并,再将该二维数组作为Dinic的输入,暂时没有想到更好的处理方式,望大佬指教。
#include <bits/stdc++.h>
using namespace std;
#define fre freopen("data.in","r",stdin);
#define ms(a) memset((a),0,sizeof(a))
#define go(i,a,b) for(register int (i)=(a);(i)<(b);++(i))
#define rep(i,a,b) for(register int (i)=(a);(i)<=(b);++(i))
#define sf(x) scanf("%d",&(x))
#define reg register
typedef long long LL;
const int inf=(0x7f7f7f7f);
const int maxn=1e2;
const int maxm=1e3;
int n;
struct node{int to,flow,next;}e[maxm<<1];
int head[maxn],cur[maxn],deep[maxn];
int cnt;
int m[100][100];
queue<int> q;
inline void add(int x,int y,int w){
e[cnt].to=y,e[cnt].flow=w,e[cnt].next=head[x];
head[x]=cnt++;
}
inline void in(){
sf(n);
memset(head,-1,sizeof(head));
char x,y;int w;
go(i,0,n){
scanf(" %c %c %d",&x,&y,&w);
// cout<<x<<y<<w;
m[x-'A'][y-'A']+=w; //将重边合并
}
go(i,0,100)go(j,0,100)
if(m[i][j]){
add(i,j,m[i][j]);
add(j,i,0);
}
}
inline bool bfs(){
ms(deep);
deep[0]=1;q.push(0);
int u,v;
while(!q.empty()){
u=q.front();q.pop();
for(int i=head[u];~i;i=e[i].next){
v=e[i].to;
if(!deep[v]&&e[i].flow){
deep[v]=deep[u]+1;
q.push(v);
}
}
}
return deep[25];
}
int dfs(int now,int nowFlow){
if(now==25)return nowFlow;
int totFlow=0;
int v;
for(int i=cur[now];~i;i=e[i].next){
cur[now]=i;v=e[i].to;
if(deep[v]==deep[now]+1&&e[i].flow){
int canFlow=0;
canFlow=dfs(v,min(nowFlow,e[i].flow));
if(!canFlow)continue;
nowFlow-=canFlow,totFlow+=canFlow;
e[i].flow-=canFlow,e[i^1].flow+=canFlow;
if(nowFlow<=0)break;
}
}
if(totFlow<=0)deep[now]=-2;
return totFlow;
}
inline void Dinic(){
int maxFlow=0;
while(bfs()){
memcpy(cur,head, sizeof(head));
maxFlow+=dfs(0,inf);
}
printf("%d
",maxFlow);
}
int main(){
in();
Dinic();
return 0;
}