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
| const int inf =0x3f3f3f3f;
const int N=505;
long long w[N][N];
long long la[N],lb[N];
bool va[N],vb[N];
long long match[N];
long long n,m,upd[N];
long long last[N];
bool dfs(int x,int fa)
{
va[x]=1;
for(int y = 1; y<=n; y++)
{
if(!vb[y])
{
if(la[x]+lb[y]-w[x][y]==0)
{
vb[y]=1;
last[y]=fa;
if(!match[y]||dfs(match[y],y))
{
match[y]=x;
return true;
}
}
else if(upd[y]>la[x]+lb[y]-w[x][y])
{
upd[y]=la[x]+lb[y]-w[x][y];
last[y]=fa;
}
}
}
return false;
}
long long KM()
{
memset(match,0,sizeof match);
memset(lb,0,sizeof lb);
for(int i = 1; i<=n; i++)
{
la[i]=w[i][1];
for(int j = 2; j<=n; j++) la[i]=max(la[i],w[i][j]);
}
for(int i = 1; i<=n; i++)
{
memset(upd,0x7f,sizeof upd);
memset(va,0,sizeof va);
memset(vb,0,sizeof vb);
memset(last,0,sizeof last);
int st=0;
match[0]=i;
while(match[st])
{
if(dfs(match[st],st)) break;
long long delta=(0x7fffffff);
for(int j = 1; j<=n; j++) if(!vb[j] && upd[j]<delta) delta=upd[j],st=j;
for(int j =1; j<=n; j++)
{
if(va[j]) la[j]-=delta;
if(vb[j]) lb[j]+=delta;
else upd[j]-=delta;
}
vb[st]=1;
}
while(st)
{
match[st]=match[last[st]];
st=last[st];
}
}
long long ans=0;
for(int i = 1; i<=n; i++) ans+=w[match[i]][i];
return ans;
}
int main()
{
memset(w,-inf,sizeof w);
cin>>n>>m;
long long u,v,c;
while(m--)
{
cin>>u>>v>>c;
w[u][v]=c;
}
cout<<KM()<<'\n';
for(int i =1 ; i<=n; i++)
{
cout<<match[i]<<' ';
}
return 0;
}
|
