每日一题-P1344

本来求边数又建了个图跑流，然后看题解发现直接流量置为A*w+1(A为足够大的数)

感觉很强

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int A=1e5;
const ll inf=1e18;
int n,m,s,t;
struct edge{
	int v;ll w;int nx;
}e[10005];
int cnt,hd[205],cur[205];
void add(int u,int v,ll w){
	e[++cnt]=edge{v,w,hd[u]};
	hd[u]=cnt;
}
int dis[205];
bool bfs(){
	queue<int> q;q.push(s);
	memset(dis,0x3f,sizeof(dis));dis[s]=0;
	for(int i=1;i<=n;i++)cur[i]=hd[i];
	while(!q.empty()){
		int u=q.front();q.pop();
		for(int i=hd[u];i;i=e[i].nx){
			int v=e[i].v;if(e[i].w<=0 || dis[v]<=dis[u]+1)continue;
			dis[v]=dis[u]+1;
			q.push(v);
		}
	}
	return dis[t]!=0x3f3f3f3f;
}
inline int rev(int id){
	if(id&1)return id+1;
	else return id-1;
}
ll dfs(int u,ll sum){
	if(u==t)return sum;
	ll res=0;
	for(int i=cur[u];i;i=e[i].nx){
		cur[u]=i;
		int v=e[i].v;if(e[i].w<=0 || dis[v]!=dis[u]+1)continue;
		ll p=dfs(v,min(sum,e[i].w));
		if(p==0)dis[v]=0x3f3f3f3f;
		e[i].w-=p;e[rev(i)].w+=p;
		res+=p;sum-=p;
	}
	return res;
}
ll dinic(){
	ll res=0;
	while(bfs())res+=dfs(s,inf);
	return res;
}
int main(){
	scanf("%d%d",&n,&m);s=1,t=n;
	for(int i=1;i<=m;i++){
		int u,v;ll w;scanf("%d%d%lld",&u,&v,&w);
		add(u,v,w*A+1);add(v,u,0);
	}
	ll res=dinic();
	printf("%lld %lld\n",res/A,res%A);
	return 0;
}