bzoj1570: [JSOI2008]Blue Mary的旅行(二分+网络流)

1570: [JSOI2008]Blue Mary的旅行

题目：传送门

题解：

　　 get到拆点新姿势，还是做题太少了...ORZ

　　因为每天就只能有一个航班，那就不能直接连了，所以要拆点（然后就被卡住了）

　　二分的话肯定是二分天数啦，这个就不说了

　　拆点的方法：把每种航班拆成天数+1（太强辣%%%Star_Feel），因为第一个点的编号是1，而到达的天数为0

　　那么这时候如果说x机场可以到y机场，那就把x机场的第i天连到y机场的第i+1天就好（代表花费了一天），流量就为机票数。

　　特别神奇...然后一通乱check就没了...ORZ%%%

　　注意答案求的是第几天，那么check的时候参数是总天数，那么就是mid+1

代码：

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cstdlib>
 4 #include<cmath>
 5 #include<algorithm>
 6 #define inf 999999999
 7 using namespace std;
 8 struct node
 9 {
10     int x,y,c,next,other;
11 }a[510000];int len,last[210000];
12 void ins(int x,int y,int c)
13 {
14     int k1,k2;
15     k1=++len;
16     a[len].x=x;a[len].y=y;a[len].c=c;
17     a[len].next=last[x];last[x]=len;
18     
19     k2=++len;
20     a[len].x=y;a[len].y=x;a[len].c=0;
21     a[len].next=last[y];last[y]=len;
22     
23     a[k1].other=k2;
24     a[k2].other=k1;
25 }
26 int n,m,T,st,ed,head,tail;
27 int list[210000],h[210000];
28 bool bt_h()
29 {
30     memset(h,0,sizeof(h));h[st]=1;
31     list[1]=st;head=1;tail=2;
32     while(head!=tail)
33     {
34         int x=list[head];
35         for(int k=last[x];k;k=a[k].next)
36         {
37             int y=a[k].y;
38             if(h[y]==0 && a[k].c>0)
39             {
40                 h[y]=h[x]+1;
41                 list[tail++]=y;
42             }
43         }
44         head++;
45     }
46     if(h[ed]>0)return true;
47     return false;
48 }
49 int find_flow(int x,int flow)
50 {
51     if(x==ed)return flow;
52     int s=0,t;
53     for(int k=last[x];k;k=a[k].next)
54     {
55         int y=a[k].y;
56         if(h[y]==h[x]+1 && a[k].c>0 && s<flow)
57         {
58             s+=t=find_flow(y,min(a[k].c,flow-s));
59             a[k].c-=t;a[a[k].other].c+=t;
60         }
61     }
62     if(s==0)h[x]=0;
63     return s;
64 }
65 struct edge
66 {
67     int x,y,c;
68 }e[510000];
69 bool check(int k)
70 {
71     len=0;memset(last,0,sizeof(last));
72     for(int i=1;i<=m;i++)
73     {
74         int x=e[i].x,y=e[i].y,c=e[i].c;
75         for(int j=1;j<k;j++)ins((x-1)*k+j,(y-1)*k+j+1,c);
76     }
77     st=0,ed=n*k+1;
78     for(int i=1;i<=k;i++)ins(st,i,T),ins((n-1)*k+i,ed,inf);
79     int ans=0;while(bt_h())ans+=find_flow(st,T);
80     if(ans>=T)return true;
81     return false;
82 }
83 int main()
84 {
85     scanf("%d%d%d",&n,&m,&T);for(int i=1;i<=m;i++)scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].c);
86     int l=0,r=n*T,ans=0;
87     while(l<=r)
88     {
89         int mid=(l+r)>>1;
90         if(check(mid+1))ans=mid,r=mid-1;
91         else l=mid+1;
92     }
93     printf("%d
",ans);
94     return 0;
95 }