【BZOJ 1877】 [SDOI2009]晨跑

 1 #include<cstdio>
 2 #include<cstring>
 3 using namespace std;
 4 const int N=25100,inf=1000000;
 5 struct ee{int to,next,f,w;}e[N*2];
 6 int S,T,cnt=1,n,k,ans,timer,m,u,v,w;
 7 int head[N],dis[N],pre[N],q[N];
 8 bool inq[N];
 9 void ins(int u,int v,int f,int w){
10     e[++cnt].to=v,e[cnt].next=head[u],e[cnt].f=f,e[cnt].w=w,head[u]=cnt;
11     e[++cnt].to=u,e[cnt].next=head[v],e[cnt].f=0,e[cnt].w=-w,head[v]=cnt;
12 }
13  
14 bool spfa(){
15     for (int i=1;i<=T;i++) dis[i]=inf;
16     int h=0,t=1;
17     q[t]=S;dis[S]=0;inq[S]=1;
18     while (h!=t){
19         int now=q[++h];if(h==2501) h=0;
20         for (int i=head[now];i;i=e[i].next){
21             int v=e[i].to;
22             if (dis[v]>dis[now]+e[i].w&&e[i].f){
23                 dis[v]=dis[now]+e[i].w;
24                 pre[v]=i;
25                 if (!inq[v]){
26                     q[++t]=v;if (t==2501) t=0;
27                     inq[v]=1;
28                 }
29             }
30         }
31         inq[now]=0;
32     }
33     if (dis[T]==inf) return 0;
34     return 1;
35 }
36  
37 void updata(){
38     int tmp=T;
39     while (tmp!=S){
40         int l=pre[tmp],v=e[l].to;
41         e[l].f-=1;e[l^1].f+=1;
42         tmp=e[l^1].to;
43     }
44     ans+=dis[T];
45 }
46  
47 int main(){
48     scanf("%d%d",&n,&m);
49     S=0;T=n*2+1;
50     ins(S,1,inf,0);ins(2*n,T,inf,0);
51     for (int i=2;i<n;i++) ins(i,i+n,1,0);
52     ins(1,1+n,inf,0);ins(n,n+n,inf,0);
53     for (int i=1;i<=m;i++){
54         scanf("%d%d%d",&u,&v,&w);
55         ins(u+n,v,1,w);
56     }
57     while (spfa()) {
58         timer++;
59         updata();
60     }
61     printf("%d %d",timer,ans);
62 }