/****************************************\
* Author : ztx
* Title : [AHOI2008] 上学路线
* ALG :
* CMT :
题意: n 点 m 双向边,边有编号和两个权值 t , c ,其中 t 代表时间
起点为 1 , 终点为 n
问
<1>计算出实际上可可和卡卡上学需要花费的最少时间并输出.
<2>帮助可可设计一个方案，删除输入信息中的一些公交路线，
使得删除后从家到学校需要的最少时间变大，而被删除路线的 c 和最小
输出删掉路线的数目, c 的和,和删除路线的方案.
分析: <1>最短路即可.
<2>求出最短路网,在最短路网上做最小割得到 c 和的最小值,
再检查一遍最短路网中哪些边的残量为0,哪些边就应该被删除.
PS : 本代码是在cogs上提交的 bzoj 只要求输出最短路和 c 和.
* Time :
\****************************************/
/****************************************\
* Author : hzoi_ztx
* Title : [AHOI2008] 上学路线
* ALG :
* CMT :
题意: n 点 m 双向边,边有编号和两个权值 t , c ,其中 t 代表时间
起点为 1 , 终点为 n
问
<1>计算出实际上可可和卡卡上学需要花费的最少时间并输出.
<2>帮助可可设计一个方案，删除输入信息中的一些公交路线，
使得删除后从家到学校需要的最少时间变大，而被删除路线的 c 和最小
输出删掉路线的数目, c 的和,和删除路线的方案.
分析: <1>最短路即可.
<2>求出最短路网,在最短路网上做最小割得到 c 和的最小值,
再检查一遍最短路网中哪些边的残量为0,哪些边就应该被删除.
PS : 本代码是在cogs上提交的 bzoj 只要求输出最短路和 c 和.
* Time :
\****************************************/
#include <cstdio>
#include <cstring>
#include <algorithm>
int CH , NEG ;
inline void read(int& ret) {
ret = NEG = 0 ; while (CH=getchar() , CH<'!') ;
if (CH == '-') NEG = true , CH = getchar() ;
while (ret = ret*10+CH-'0' , CH=getchar() , CH>'!') ;
if (NEG) ret = -ret ;
}
#define maxn 2510LL
#define maxm 125000LL
struct FST { int to , next , len , flow , id ; } re[maxm<<1] , e[maxm<<1] ;
int star[maxn] = {0} , tote = 1 , rstar[maxn] = {0} , rtote = 1 ;
inline void AddEdge(int u , int v , int cap , int id) {
e[++tote].to = v ; e[tote].flow = cap ; e[tote].next = star[u] ; star[u] = tote ; e[tote].id = id ;
e[++tote].to = u ; e[tote].flow = 0 ; e[tote].next = star[v] ; star[v] = tote ;
}
inline void AddREdge(int u , int v , int t , int c , int id) {
re[++rtote].to = v ; re[rtote].len = t ; re[rtote].flow = c ;
re[rtote].id = id ; re[rtote].next = rstar[u] ; rstar[u] = rtote ;
re[++rtote].to = u ; re[rtote].len = t ; re[rtote].flow = c ;
re[rtote].id = id ; re[rtote].next = rstar[v] ; rstar[v] = rtote ;
}
#define infi 0x3f3f3f3fLL
#define min(x,y) ((x)<(y)?(x):(y))
int N , S , T ;
int h[maxn] , vh[maxn] ;
int dfs(int u , int flowu) {
int p , tmp = h[u]+1 , flow = 0 , flowv ;
if (u == T) return flowu ;
for (p = star[u] ; p ; p = e[p].next) {
if (e[p].flow && (h[e[p].to]+1==h[u])) {
flowv = dfs(e[p].to , min(flowu-flow , e[p].flow)) ;
flow += flowv ; e[p].flow -= flowv ; e[p^1].flow += flowv ;
if (flow==flowu || h[S]==N) return flow ;
}
}
for (p = star[u] ; p ; p = e[p].next)
if (e[p].flow) tmp = min(tmp , h[e[p].to]) ;
if (--vh[h[u]] == 0) h[S] = N ;
else ++ vh[h[u]=tmp+1] ;
return flow ;
}
int SAP() {
int ret = 0 ;
memset(vh , 0 , sizeof vh) ;
memset(h , 0 , sizeof h) ;
vh[S] = N ;
while (h[S] < N) ret += dfs(S , infi) ;
return ret ;
}
#define sizeque 777LL
int q[sizeque] , head , tail ;
inline int F(int x) { return ((x%sizeque)+sizeque)%sizeque ; }
inline void clear() { head = 0 , tail = -1 ; }
inline int front() { return q[F(head)] ; }
inline int back() { return q[F(tail)] ; }
inline void push_front(int x) { q[F(--head)] = x ; }
inline void push_back(int x) { q[F(++tail)] = x ; }
inline void pop_front() { head ++ ;}
inline void pop_back() { tail -- ; }
inline bool empty() { return head > tail ; }
bool exist[maxn] = {0} ;
int dis1[maxn] , disn[maxn] ;
void SPFA(int S , int *dis) {
int u , v , p ;
clear() ; dis[S] = 0 ; push_back(S) ;
while (!empty()) {
u = front() ; pop_front() ; exist[u] = false ;
for (p = rstar[u] ; p ; p = re[p].next) {
v = re[p].to ;
if (dis[v] > dis[u]+re[p].len) {
dis[v] = dis[u]+re[p].len ;
if (!exist[v]) {
exist[v] = true ;
if (!empty() && dis[v]<dis[front()]) push_front(v) ;
else push_back(v) ;
}
}
}
}
}
int ans[maxm] = {0} , ansc ;
int main() {
int i , p , u , v , t , c , m , n ;
#define READ
#ifdef READ
freopen("routez.in" ,"r",stdin ) ;
freopen("routez.out","w",stdout) ;
#endif
read(n) , read(m) ;
for (i = 1 ; i <= m ; i ++ ) {
read(u) , read(v) , read(t) , read(c) ;
AddREdge(u , v , t , c , i) ;
}
memset(dis1 , 0x3f , sizeof dis1) ;
SPFA(1 , dis1) ;
memset(disn , 0x3f , sizeof disn) ;
SPFA(n , disn) ;
printf("%d\n", dis1[n]) ;
for (u = 1 ; u <= n ; u ++ ) {
for (p = rstar[u] ; p ; p = re[p].next) {
v = re[p].to ;
if (dis1[u]+re[p].len+disn[v] == dis1[n]) {
AddEdge(u , v , re[p].flow , re[p].id) ;
}
}
}
N = n , S = 1 , T = n ;
ansc = SAP() ;
for (u = 1 ; u <= n ; u ++ ) {
for (p = star[u] ; p ; p = e[p].next) {
if (p&1) continue ;
if (e[p].flow == 0) ans[++ans[0]] = e[p].id ;
}
}
std::sort(ans+1 , ans+ans[0]+1) ;
printf("%d %d\n", ans[0] , ansc) ;
for (i = 1 ; i <= ans[0] ; i ++ ) {
printf("%d\n", ans[i]) ;
}
#ifdef READ
fclose(stdin) ; fclose(stdout) ;
#else
getchar() ; getchar() ;
#endif
return 0 ;
}
评论 (0)