看到要求两个量就下意识的想到了费用流= =,先把一个点拆成两个点就能够解决一个的只经过一次的限制
CODE:
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
#define maxn 410
#define maxm 50000
#define inf 0x7fffffff
struct edges{
int to,next,cap,dist;
}edge[maxm];
int next[maxn],l;
int s,t;
int addedge(int x,int y,int z,int cap){
l++;
edge[l*2]=(edges){y,next[x],cap,z};
edge[l*2+1]=(edges){x,next[y],0,-z};
next[x]=l*2;next[y]=l*2+1;
return 0;
}
int dist[maxn],way[maxn],cost;
bool b[maxn];
queue<int> q;
bool spfa(){
for (int i=1;i<=t;i++) dist[i]=inf;
dist[s]=0;
q.push(s);
while (!q.empty()){
int u=q.front();q.pop();
b[u]=0;
for (int i=next[u];i;i=edge[i].next)
if (edge[i].cap&&dist[edge[i].to]>dist[u]+edge[i].dist){
dist[edge[i].to]=dist[u]+edge[i].dist;
way[edge[i].to]=i;
if(!b[edge[i].to]){
b[edge[i].to]=1;
q.push(edge[i].to);
}
}
}
if (dist[t]==inf) return 0;
return 1;
}
int mcmf(){
int fl=0;
while (spfa()){
int flow=inf,x=t;
while (x!=s){
flow=min(flow,edge[way[x]].cap);
x=edge[way[x]^1].to;
}
cost+=dist[t]*flow;fl+=flow;
x=t;
while (x!=s){
edge[way[x]].cap-=flow;
edge[way[x]^1].cap+=flow;
x=edge[way[x]^1].to;
}
}
return fl;
}
int main(){
int n,m,S;
scanf("%d%d",&n,&m);
for (int i=2;i<n;i++) addedge(i*2,i*2+1,0,1);
for (int j=1;j<=m;j++) {
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
addedge(x*2+1,y*2,z,1);
}
s=3;t=n*2;
printf("%d ",mcmf());
printf("%d",cost);
return 0;
}