1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
| #include <algorithm>
#include <bitset>
#include <map>
#include <vector>
#include <string>
#include <cstring>
#include <iostream>
#include <cmath>
#include <stack>
#include <set>
#include<queue>
using namespace std;
const double eps = 1e-10;
const double pi = 3.1415926535897932384626433832795;
const double eln = 2.718281828459045235360287471352;
#define f(i, a, b) for (int i = a; i <= b; i++)
#define LL long long
#define IN freopen("in.txt", "r", stdin)
#define OUT freopen("out.txt", "w", stdout)
#define scan(x) scanf("%d", &x)
#define mp make_pair
#define pb push_back
#define sqr(x) (x) * (x)
#define pr1(x) printf("Case %d: ", x)
#define pn1(x) printf("Case %d:\n", x)
#define pr2(x) printf("Case #%d: ", x)
#define pn2(x) printf("Case #%d:\n", x)
#define lowbit(x) (x & (-x))
#define fi first
#define se second
#define sz(x) int((x).size())
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define summ(a) (accumulate(all(a), 0ll))
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;
const int N = 5e3 + 5, M = 1e5 + 5;
const int INF = 0x3f3f3f3f;
int n, m, tot = 1, lnk[N], cur[N], ter[M], nxt[M], cap[M], cost[M], dis[M], ret;
bool vis[N];
void add(int u, int v, int w, int c)
{
ter[++tot] = v, nxt[tot] = lnk[u], lnk[u] = tot, cap[tot] = w, cost[tot] = c;
}
void addedge(int u,int v,int w,int c){
add(u,v,w,c);
add(v,u,0,-c);
}
bool spfa(int s,int t){
memset(dis,0x3f,sizeof(dis));
memcpy(cur,lnk,sizeof(lnk));
queue<int >q ;
q.push(s),dis[s]=0,vis[0]=1;
while(!q.empty()){
int u=q.front();
q.pop(),vis[u]=0;
for(int i=lnk[u];i;i=nxt[i]){
int v=ter[i];
if(cap[i]&&dis[v]>dis[u]+cost[i]){
dis[v]=dis[u]+cost[i];
if(!vis[v])q.push(v),vis[v]=1;
}
}
}
return dis[t]!=INF;
}
int dfs(int u,int t,int flow){
if(u==t)return flow;
vis[u]=1;
int ans=0;
for(int &i=cur[u];i&&ans<flow;i=nxt[i]){
int v=ter[i];
if(!vis[v]&&cap[i]&&dis[v]==dis[u]+cost[i]){
int x=dfs(v,t,min(cap[i],flow-ans));
if(x)ret+=x*cost[i],cap[i]-=x,cap[i^1]+=x,ans+=x;
}
}
vis[u]=0;
return ans;
}
int mcmf(int s,int t){
int ans=0;
while(spfa(s,t)){
int x;
while((x=dfs(s,t,INF)))ans+=x;
}
return ans;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m;
f(i,1,n-1){
addedge(i,i+n,1,0);
}
while(m--){
int a,b,c;
cin>>a>>b>>c;
addedge(a+n,b,1,c);
}
int ans=mcmf(1+n,n);
cout<<ans<<" "<<ret;
return 0;
}
|