Problem Description: There are N nodes and M edges, you can go through each node at most once, there are weights on the edges. Try to minimize the total weight going through 1 to N while maximizing the times you can go from 1 to N without passing through any nodes twice except node 1 and node N. Note that the edge between 1 and N exists, and you can at most pass through this edge once.
Input Format:
The first line contains two numbers N and M.
The next M lines contain three integers u,v and w denotes a directed edge going from u to v with weight w.
Output Format:
Two numbers in one line. The first number denotes the maximum times and the second number represents the minimum total weight.
Sample Input:
7 10
1 2 1
1 3 1
2 4 1
3 4 1
4 5 1
4 6 1
2 5 5
3 6 6
5 7 1
6 7 1
Sample Output:
2 11
Solution: This is a classical maximum flow minimum cost problem. The only hard point is to achieve the requirement that each node can be only passed through once. We can do this by making each point into two points with capacity one, which limits the flow passing through this node. Also, remember to write a special judge on point 1 and N, since they have to have infinite capacity as source and end point.
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <stdio.h>
#include <fstream>
#include <cmath>
#include <stdlib.h>
#include <iomanip>
#include <algorithm>
#include <limits.h>
#include <stack>
using namespace std;
#define FAST_IO ios::sync_with_stdio(false);
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
typedef pair<double,double> pdd;
typedef long long ll;
#define inf 0x7f7f7f7f
const int maxn = 1005;
int N,M;
struct edge{
int from,to,cap,flow,cost;
edge(int a = 0,int b = 0,int c = 0,int d = 0,int e = 0):from(a),to(b),cap(c),flow(d),cost(e){}
};
vector<edge> es;
vector<int> G[maxn];
int dis[maxn],S,T;
bool vis[maxn];
void addedge(int from,int to,int cap,int cost){
es.push_back(edge(from,to,cap,0,cost));
es.push_back(edge(to,from,0,0,-cost));
int m = es.size();
G[from].push_back(m - 2);
G[to].push_back(m - 1);
}
bool spfa(){
memset(dis,0x7f,sizeof(dis));
memset(vis,0,sizeof(vis));
dis[S] = 0;
vis[S] = 1;
queue<int> q;
q.push(S);
while(!q.empty()){
int u = q.front(); q.pop();
for(int i = 0; i < G[u].size(); i++){
edge e = es[G[u][i]];
if(e.cap && dis[e.to] > dis[u] + e.cost){
dis[e.to] = dis[u] + e.cost;
if(!vis[e.to]){
vis[e.to] = 1;
q.push(e.to);
}
}
}
vis[u] = 0;
}
return dis[T] != inf;
}
int ans = 0;
int dfs(int x,int f){
if(x == T) return f;
vis[x] = 1;
int w,used = 0;
for(int i = 0; i < G[x].size(); i++){
edge &e = es[G[x][i]];
edge &er = es[G[x][i] ^ 1];
if(e.cap && !vis[e.to] && dis[e.to] == dis[x] + e.cost){
w = f - used;
w = dfs(e.to,min(w,e.cap));
ans += w * e.cost;
e.cap -= w; er.cap += w; used += w;
if(used == f) return f;
}
}
return used;
}
int zkw(){
int flow = 0;
while(spfa()){
vis[T] = 1;
while(vis[T]){
memset(vis,0,sizeof(vis));
flow += dfs(S,inf);
}
}
return flow;
}
int main(){
FAST_IO
cin>>N>>M;
for(int i = 2; i <= N - 1; i++){
addedge(i,i + N,1,0);
}
addedge(1,1 + N,inf,0); addedge(N, 2 * N,inf,0);
for(int i = 1; i <= M; i++){
int u,v,w;
cin>>u>>v>>w;
addedge(u + N,v,1,w);
}
S = 1, T = 2 * N;
int day = zkw();
cout<<day<<" "<<ans<<endl;
}