ztx

[AHOI2008] 上学路线

Posted on 2015年1月13日 10:47
/****************************************\
* 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 ;
}