Posted Updated  Semprathlon / Simfae Dean ACM-ICPC / Programinga minute read (About 156 words)

2015 Multi-University Training Contest 5

1009 MZL’s Border

字符串是可递归形式构造的，求解也是递归的；
但是递归时划分的三种情况，最终并没有做好化归 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import java.io.*;
import java.util.*;
import java.math.*;
public class Main{
    static BigInteger f[] = new BigInteger[1005];
    public static void main(String[] args){
        f[1] = new BigInteger("1");
        f[2] = new BigInteger("2");
        for(int i = 3; i <= 1001; i++)
            f[i] = f[i - 1].add(f[i - 2]);
        Scanner cin = new Scanner(System.in);
        int T = cin.nextInt();
        int n;
        BigInteger m;
        for(int cas = 1; cas <= T; cas++){
            n = cin.nextInt();
            m = cin.nextBigInteger();
            BigInteger mm = m.add(new BigInteger("1"));
            int p = 0;
            for(int i = 1; i <= 1001; i++){
                if(f[i].compareTo(mm) > 0){
                    p = i;
                    break;
                }
            }
            BigInteger ans = m.subtract(f[p - 2]);
            System.out.println(ans.mod(new BigInteger("258280327")));
        }
        
    }
}
Posted Updated  Semprathlon / Simfae Dean ACM-ICPC / Programing3 minutes read (About 436 words)

2015 Multi-University Training Contest 4

1009 Walk Out

状态压缩方面，虽然想到了用一维的x+y替代二维的x,y，但并没有做到位。
既然可以转化成二维DP，还有何搜索必要
寻找合适的出发点时，不要陷入“极近点”而丢失了“最近点”！ 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include<cctype>

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<queue>
#include<stack>
#include<set>
#include<map>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int inf=0x7fffffff;
const double eps=1e-3;

typedef pair<int,int> pr;
const int dir[4][2]={ {0,-1},{0,1},{-1,0},{1,0}};
const int maxn=1010;
const int maxm=1010;
int n,m,X0,Y0;
bool g[maxn][maxm],f[maxn][maxm],vis[maxn][maxm];
char str[maxn];

bool can(int x,int y){
    if (x<1||x>n||y<1||y>m) return 0;
    return 1;
}
bool can(pr p){
    return can(p.first,p.second);
}
int mdis(int x,int y){
    return abs(x-n)+abs(y-m);
}
int mdis(pr p){
    return mdis(p.first,p.second);
}
int geth(pr p){
    return p.first+p.second;
}

void find0(int x,int y){
        if (vis[x][y]||!can(x,y)) return;
        vis[x][y]=1;
        if (g[x][y]) return;
        f[x][y]=1;
        if (x+y>X0+Y0)
        {
            X0=x;Y0=y;
        }
        for(int i=0;i<4;i++) find0(x+dir[i][0],y+dir[i][1]);
}


int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {

        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
        {
            scanf("%s",str+1);
            for(int j=1;j<=m;j++)
            {
                if (str[j]=='1') g[i][j]=1;
                else g[i][j]=0;
            }
        }

        X0=0;Y0=0;
        memset(vis[0],0,maxn*maxm*sizeof(vis[0][0]));
        memset(f[0],0,maxn*maxm*sizeof(f[0][0]));
        find0(1,1);
        //cout<<X0<<' '<<Y0<<endl;
        if (X0+Y0==n+m){
            printf("%d\n",0);
            continue;
        }
        if (X0+Y0<2)
        {
            X0=1;Y0=1;
            f[1][1]=1;
            printf("1");
        }
        for(int i=X0+Y0;i<n+m;i++)
        {
            int k=1;
            for(int j=max(1,i-m);j<=min(n,i-1);j++)
                if (f[j][i-j])
            {
                int k1=j<n?g[j+1][i-j]:1;
                int k2=i-j<m?g[j][i-j+1]:1;
                k=min(k,min(k1,k2));
            }
            for(int j=max(1,i-m);j<=min(n,i-1);j++)
                if (f[j][i-j])
            {
                int k1=j<n?g[j+1][i-j]:1;
                int k2=i-j<m?g[j][i-j+1]:1;
                if (k1==k) f[j+1][i-j]=1;
                if (k2==k) f[j][i-j+1]=1;
            }
            printf("%d",k);
        }
        puts("");
    }
    return 0;
}
Posted Updated  Semprathlon / Simfae Dean ACM-ICPC / Programing4 minutes read (About 633 words)

2015 Multi-University Training Contest 3

1001 Magician

具有肉眼可见的可用线段树解决的统计操作要求。
但是区间更新异常繁杂。
不要拘泥于区间内具体的数据选取，而应该采用状态转移。
除了向上传递操作以外，注意查询操作时不要把区段查询结果直接更新到左右子树上（覆盖区域并不一致） 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
/**
 * 2015年7月29日 上午10:35:39
 * PrjName:hdu5316-2
 * @ Semprathlon
 */
import java.io.*;
import java.util.*;

public class Main {
    final static long inf=0x4000000000000000L;
    final static int maxn=100010;
    static int[] a=new int[maxn+1];
    static SegTree tr=new SegTree(1, maxn);
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        InputReader in=new InputReader(System.in);
        PrintWriter out=new PrintWriter(System.out);
        int T=in.nextInt();
        while(T-->0){
            int n=in.nextInt();
            int m=in.nextInt();
            for(int i=1;i<=n;i++) 
                a[i]=in.nextInt();
            tr.reset(1,1, n, a);
            for(int i=1;i<=m;i++){
                int k=in.nextInt();
                int x=in.nextInt();   
                if (k==0){
                    //out.println(tr.query(x, y));
                    int y=in.nextInt();
                    long ans=-inf;
                    long[] res=tr.query(1,x, y);
                    for(int j=0;j<4;j++)
                        ans=Math.max(ans, res[j]);
                    out.println(ans);
                }
                else{
                    long y=in.nextLong();
                    tr.update(1,x, y);
                }
                    
            }
        }
        out.flush();
        out.close();
    }

}

class SegTree{
    final static long inf=0x4000000000000000L;
    int[] l,r,mid;
    long[][] s;
    SegTree(int x,int y){
        l=new int[(y-x+2)<<2];
        r=new int[(y-x+2)<<2];
        mid=new int[(y-x+2)<<2];
        s=new long[(y-x+2)<<2][4];
        build(1,x,y);
    }
    void build(int k,int x,int y){
        /*l=x;r=y;*/mid[k]=(x+y)>>1;
        if (x<y){
            build(k<<1,x, mid[k]);
            build(k<<1|1,mid[k]+1, y);
        }
        //s0=s1=s2=s3=-inf;
    }
    void reset(int k,int x,int y,int[] a){
        l[k]=x;r[k]=y;mid[k]=(x+y)>>1;
        if (x<y){
            reset(k<<1,x, mid[k], a);
            reset(k<<1|1,mid[k]+1, y, a);
            up(s[k],s[k<<1],s[k<<1|1]);
        }
        else{
            if ((mid[k]&1)>0){//odd
                s[k][0]=a[mid[k]];
                s[k][1]=s[k][2]=s[k][3]=-inf;
            }
            else{//even
                s[k][3]=a[mid[k]];
                s[k][0]=s[k][1]=s[k][2]=-inf;
            }
        }
            
    }
    void up(long[] k,long[] l,long[] r){
        k[0]=k[1]=k[2]=k[3]=-inf;
        k[0]=Math.max(k[0], l[0]+r[2]);//odd-odd
        k[0]=Math.max(k[0], l[1]+r[0]);
        
        k[1]=Math.max(k[1], l[1]+r[1]);//odd-even
        k[1]=Math.max(k[1], l[0]+r[3]);
        
        k[2]=Math.max(k[2], l[2]+r[2]);//even-odd
        k[2]=Math.max(k[2], l[3]+r[0]);
        
        k[3]=Math.max(k[3], l[3]+r[1]);//even-even
        k[3]=Math.max(k[3], l[2]+r[3]);
        
        k[0]=Math.max(k[0], l[0]);
        k[0]=Math.max(k[0], r[0]);
        
        k[1]=Math.max(k[1], l[1]);
        k[1]=Math.max(k[1], r[1]);
        
        k[2]=Math.max(k[2], l[2]);
        k[2]=Math.max(k[2], r[2]);
        
        k[3]=Math.max(k[3], l[3]);
        k[3]=Math.max(k[3], r[3]);
    }
    long[] query(int k,int x,int y){
        long[] res=new long[4];
        if (x==l[k]&&r[k]==y){
            res=s[k].clone();
        }
        else{
            long[] L,R;
            if (x<=mid[k]) L=query(k<<1,x,Math.min(y, mid[k])).clone();
            else L=new long[]{-inf,-inf,-inf,-inf};
            if (mid[k]<y) R=query(k<<1|1,Math.max(mid[k]+1, x),y).clone();
            else R=new long[]{-inf,-inf,-inf,-inf};
            up(res,L,R);
        }
        return res;
    }
    void update(int k,int x,long d){
        if (l[k]==r[k]){
            if ((mid[k]&1)>0){//odd
                s[k][0]=d;
                s[k][1]=s[k][2]=s[k][3]=-inf;
            }
            else{//even
                s[k][3]=d;
                s[k][0]=s[k][1]=s[k][2]=-inf;
            }
            return;
        }
        if (x<=mid[k]) update(k<<1,x,d);
        if (mid[k]<x) update(k<<1|1,x,d);
        up(s[k],s[k<<1],s[k<<1|1]);
    }
}

class InputReader{
    public BufferedReader reader;
    public StringTokenizer tokenizer;

    public InputReader(InputStream stream){
           reader = new BufferedReader(new InputStreamReader(stream), 32768);
           tokenizer = null;
    }

    public String next(){
        while(tokenizer == null || !tokenizer.hasMoreTokens()){
            try{
                tokenizer = new StringTokenizer(reader.readLine());
            }catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken();
    }

    public int nextInt() {
        return Integer.parseInt(next());
    }

    public long nextLong() {
        return Long.parseLong(next());
    }
}

1010 Crazy Bobo

Posted Updated  Semprathlon / Simfae Dean ACM-ICPC / Programinga minute read (About 133 words)

2015 Multi-University Training Contest 2

1002 Buildings

特别拐弯抹角的平面几何模拟计算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<cctype>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<queue>
#include<stack>
#include<set>
#include<map>

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
const int maxn=210;
const int inf=0x7fffffff;
const double eps=1e-3;

int N,M;


int main()
{
    int x,y;
    while(~scanf("%d%d%d%d",&N,&M,&x,&y))
    {
        if (M<N)
        {
            swap(N,M);
            swap(x,y);
        }
            int t0=(N+1)>>1;
            int up=x-1;
            int down=N-x;
            int left=y-1;
            int right=M-y;
            //cout<<t0<<endl;
            if ((N&1)&&N==M&&x==y&&x==(N+1)/2)
                printf("%d\n",t0-1);
            /*else if (min(up,down)>t0)
                printf("%d\n",min(max(left,right),min(up,down)));*/
            else
            {
                x=min(x,N-x+1);
                y=min(y,M-y+1);
                t0=max(t0,min(N-x,y));
                t0=min(t0,(M+1)/2);
                printf("%d\n",t0);
            }

    }
    return 0;
}
Posted Updated  Semprathlon / Simfae Dean ACM-ICPC / Programing9 minutes read (About 1292 words)

2015 Multi-University Training Contest 1

1002 Assignment RMQ

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
/**
 * 2015年7月21日 下午1:40:29
 * PrjName:0721-02
 * @ Semprathlon
 */
import java.io.*;
import java.util.*;
public class Main {
    final static int maxm=20,maxn=100010;
    static int[] a;
    static int[][] maxsum,minsum;
    static int n,k;
    
    static void RMQ(){ //预处理->O(nlogn){
        for(int i = 1; i != maxm; ++i)
            for(int j = 1; j <= n; ++j)
                if(j + (1 << i) - 1 <= n){
                    maxsum[i][j] = Math.max(maxsum[i - 1][j], maxsum[i - 1][j + (1 << i >> 1)]);
                    minsum[i][j] = Math.min(minsum[i - 1][j], minsum[i - 1][j + (1 << i >> 1)]);
                }
    }
    
    static int query(int src,int des){
        int k = (int)(Math.log(des - src + 1.0) / Math.log(2.0));
        int maxres = Math.max(maxsum[k][src], maxsum[k][des - (1 << k) + 1]);
        int minres = Math.min(minsum[k][src], minsum[k][des - (1 << k) + 1]);
        return maxres-minres;
    }
    
    static int bisearch(int p){
        int l=p,r=n;
        int res=p;
        while(l<=r){
            int mid=(l+r)>>1;
            int dif=query(p,mid);
            if (dif<k){
                res=mid;l=mid+1;
            }
            else
                r=mid-1;
        }
        return res-p+1;
    }
    
    public static void main(String[] args) throws IOException{
        // TODO Auto-generated method stub
        InputReader in=new InputReader(System.in);
        PrintWriter out=new PrintWriter(System.out);
        int T=in.nextInt();
        while(T-->0){
            n=in.nextInt();
            k=in.nextInt();
            a=new int[n+1];
            maxsum=new int[maxm][n+1];
            minsum=new int[maxm][n+1];
            for(int i=1;i<=n;i++){
                a[i]=in.nextInt();
                maxsum[0][i]=minsum[0][i]=a[i];
            }
            RMQ();
            long res=0L;
            for(int i=1;i<=n;i++)
                //out.print(bisearch(i)+" ");
                res+=bisearch(i);
            out.println(res);
        }
        out.flush();
        out.close();
    }

}

class InputReader{
    public BufferedReader reader;
    public StringTokenizer tokenizer;

    public InputReader(InputStream stream){
           reader = new BufferedReader(new InputStreamReader(stream), 32768);
           tokenizer = null;
    }

    public String next(){
        while(tokenizer == null || !tokenizer.hasMoreTokens()){
            try{
                tokenizer = new StringTokenizer(reader.readLine());
            }catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken();
    }

    public int nextInt() {
        return Integer.parseInt(next());
    }

    public long nextLong() {
        return Long.parseLong(next());
    }
}

1007 Tricks Device

netflow,maxflow,Dinic

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
/**
 * 2015年7月22日 上午10:07:44
 * PrjName:0721-07
 * @ Semprathlon
 */
import java.io.*;
import java.util.*;

class Edge{
    int to,cap,rev,next;
    Edge(){}
    Edge(int t,int w,int r,int nt){
        to=t;cap=w;rev=r;next=nt;
    }
    Edge(Edge e){
        this.to=e.to;
        this.cap=e.cap;
        this.rev=e.rev;
        this.next=e.next;
    }
    void set(int t,int w,int r,int nt){
        to=t;cap=w;rev=r;next=nt;
    }
    void set(Edge e){
        this.to=e.to;
        this.cap=e.cap;
        this.rev=e.rev;
        this.next=e.next;
    }
}
class Queue<T>{
    T[] data;
    int size,h,r;
    /*Queue(Class<T> c,int sz){
        size=sz;
        @SuppressWarnings("unchecked")
        final T[] tmp=(T[])Array.newInstance(c, sz);
        data=tmp;
    }*/
    Queue(int sz){
        size=sz;
        data=(T[])new Object[sz];
    }
    void clear(){
        h=r=0;
    }
    boolean empty(){
        return h==r;
    }
    boolean full(){
        return (r+1)%size==h;
    }
    void push(T n){
        data[r]=n;
        r=(r+1)%size;
    }
    T pop(){
        T tmp=data[h];
        h=(h+1)%size;
        return tmp;
    }
}

public class Main {
    static int[] head,dis,cnt;
    static boolean[] vis;
    static Edge[] G;
    static int n,m;
    static Queue<Integer> que;
    static void bfs(int st){
        Arrays.fill(dis, -1);
        que.clear();
        dis[st]=0;
        vis[st]=true;
        que.push(st);
        while(!que.empty()){
            int u=que.pop();
            for(int i=head[u];i>-1;i=G[i].next){
                int v=G[i].to;
                if (G[i].cap>0&&!vis[v]){
                    dis[v]=dis[u]+1;
                    que.push(v);
                    vis[v]=true;
                }
            }
        }
    }
    static int dfs(int u,int d){
        if (u==n) return d;
        int res=0;
        for(int i=head[u];i>-1;i=G[i].next){
            int v=G[i].to;
            if (G[i].cap>0&&dis[v]==dis[u]+1){
                int tmp=dfs(v,Math.min(d,G[i].cap));
                G[i].cap-=tmp;
                G[G[i].rev].cap+=tmp;
                d-=tmp;
                res+=tmp;
            }
        }
        return res;
    }
    static int max_flow(int s,int t){
        int res=0;
        for(;;){
            Arrays.fill(vis, false);
            bfs(s);
            if (!vis[t]) return res;
            res+=dfs(s,Integer.MAX_VALUE);
        }
    }
    static void addedge(int from,int to,int cap){
        G[head[0]]=new Edge(to, cap, head[0]+1, head[from]);
        head[from]=head[0]++;
        G[head[0]]=new Edge(from,cap,head[0]-1,head[to]);
        head[to]=head[0]++;
    }
    static void spfa(int st){
        que.clear();
        que.push(st);
        dis[st]=0;
        vis[st]=true;
        while(!que.empty()){
            int u=que.pop();vis[u]=false;
            for(int i=head[u];i>-1;i=G[i].next){
                int v=G[i].to;
                if (dis[u]+G[i].cap<dis[v]){
                    dis[v]=dis[u]+G[i].cap;
                    if (!vis[v]){ 
                        que.push(v);
                        vis[v]=true;
                    }
                }
            }
        }
    }
    static int spfa2(int s,int t){
        Arrays.fill(cnt, Integer.MAX_VALUE);
        Arrays.fill(vis, false);
        que.clear();
        que.push(s);
        cnt[s]=0;
        vis[s]=true;
        while(!que.empty()){
            int u=que.pop();vis[u]=false;
            for(int i=head[u];i>-1;i=G[i].next){
                int v=G[i].to;
                if (dis[u]+G[i].cap!=dis[v]) continue;
                if (!vis[v]){ 
                    que.push(v);
                    vis[v]=true;
                }
                cnt[v]=Math.min(cnt[v], cnt[u]+1);
            }
            
        }
        return cnt[t];
    }
    static void init(){
        G=new Edge[(m<<1)+1];
        head=new int[(m<<1)+1];
        dis=new int[n+1];
        cnt=new int[n+1];
        vis=new boolean[n+1];
        Arrays.fill(head, -1);
        Arrays.fill(dis, Integer.MAX_VALUE);
        head[0]=1;
        //que=new Queue(Integer.class,(m<<1)+1);
        que=new Queue<Integer>((m<<1)+1);
    }
    public static void main(String[] args) throws IOException,InterruptedException {
        // TODO Auto-generated method stub
        StreamTokenizer cin = new StreamTokenizer(new BufferedInputStream(System.in)); 
        //InputReader in=new InputReader(System.in);
        PrintWriter out=new PrintWriter(System.out);
        while(cin.nextToken()!=StreamTokenizer.TT_EOF){
            n=(int)cin.nval;
            cin.nextToken();
            m=(int)cin.nval;
            init();
            for(int i=1;i<=m;i++){
                cin.nextToken();
                int u=(int)cin.nval;
                cin.nextToken();
                int v=(int)cin.nval;
                cin.nextToken();
                int w=(int)cin.nval;
                addedge(u, v, w);
                //addedge(v, u, w);
            }
            spfa(1);
            //out.println(dis[n]);
            //max_flow(1, n);
            //init2();
            Dinic dinic=new Dinic(1, n);
            for(int u=1;u<=n;u++)
                for(int i=head[u];i>-1;i=G[i].next){
                    int v=G[i].to;
                    if (dis[u]+G[i].cap==dis[v])
                        dinic.add(u, v, 1);
                }
            /*init();
            for(int i=1;i<=U[0];i++)
                addedge(U[i],V[i].to,1);*/
            out.println(dinic.maxflow()+" "+(m-spfa2(1,n)));
            /*for(int i=1;i<=n;i++)
                for(int j=head[i];j>-1;j=G[j].next)
                    out.println(j+"\t:"+i+" "+G[j].to+" "+G[j].cap+" "+G[j].rev+" "+G[j].next);*/
            
        }
        out.flush();
        out.close();
    }

}

class Dinic{
    public Dinic(int sourse , int meet){
                 this.sourse = sourse ; 
                 this.meet = meet ;
                 Arrays.fill(g,  0) ;
                 id = 1 ;
    }

    static final  int  maxn = 2008 , maxm = 500000 ;
    static class Edge{
           int v , f ,next ;
           Edge(){}
           Edge(int _v , int _f , int _next){
                 this.v = _v ;
                 this.f = _f ;
                 this.next = _next ;
           }
    };
    int  sourse , meet ;
    int  id ;
    static Edge[] e = new Edge[maxm*2 + 10] ;
    static int[] g = new int[maxn + 10] ;

    public void  add(int u , int v , int f){
              e[++id] = new Edge(v , f ,g[u]) ;
              g[u] = id ;
              e[++id] = new Edge(u , 0 , g[v]) ;
              g[v] = id ;
    }

    Queue<Integer> que  = new Queue<Integer>(maxm);
    static boolean[] vis = new boolean[maxn + 10] ;
    static int[]  dist = new int[maxn + 10] ;

    void bfs(){
             Arrays.fill(dist, 0) ;
             while(! que.empty()) que.pop() ;
             que.push(sourse) ;
             vis[sourse] = true ;
             while(! que.empty()){
                  int u = que.pop() ;
                  for(int i = g[u] ; i > 0 ; i = e[i].next){
                       int v = e[i].v ;
                       if(e[i].f  > 0 && !vis[v]){
                             que.push(v) ;
                             dist[v] = dist[u] + 1 ;
                             vis[v] = true ;
                       }
                  }
             }
    }

    int  dfs(int u , int delta){
             if(u == meet) return delta ;
             int ans = 0 ;
             for(int i = g[u] ; i > 0  && delta > 0  ; i = e[i].next){
                   int  v = e[i].v ;
                   if(e[i].f  > 0 && dist[v] == dist[u] + 1){
                        int d = dfs(v , Math.min(delta , e[i].f)) ;
                        e[i].f -= d ;
                        e[i^1].f += d ;
                        delta -= d ;
                        ans += d ;
                   }
             }
             return ans ;
    }

    public int  maxflow(){
                 int ans = 0 ;
                 while(true){
                     Arrays.fill(vis, false) ;
                     bfs() ;
                     if(! vis[meet]) return ans  ;
                     ans += dfs(sourse , Integer.MAX_VALUE) ;
                 }
    }

}

class InputReader{
    public BufferedReader reader;
    public StringTokenizer tokenizer;

    public InputReader(InputStream stream){
           reader = new BufferedReader(new InputStreamReader(stream), 32768);
           tokenizer = null;
    }

    public String next(){
        while(tokenizer == null || !tokenizer.hasMoreTokens()){
            try{
                tokenizer = new StringTokenizer(reader.readLine());
            }catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken();
    }

    public int nextInt() {
        return Integer.parseInt(next());
    }

    public long nextLong() {
        return Long.parseLong(next());
    }

}

特别复杂的套模板

Follow

Categories

Tags

ACM-ICPC14
AC自动机1
AWS2
Adobe1
Angular1
Apache1
Arch Linux2
BFS2
BIT3
Bestcoder23
Bitset3
Bootstrap1
C++2
CCPC1
Catalan1
CentOS3
Clover2
Compiler1
Contest6
Cpp1
DFS3
DNS1
DP13
DSDT3
Data Analytics2
Dinic1
Docker1
Eclipse1
Expect1
Fibonacci1
Frontend1
GLUT1
GPT1
GUI1
Gentoo1
Geometry1
Git1
Github2
Graduate1
HTML1
Hash2
Heap1
Interview1
JNUOJ1
Java12
K8s1
KMP1
Linux3
Live Archive2
MBR1
MS=DOS1
Mac14
Manhattan1
Multi-Uni5
MySQL8
Möbius反演1
NAS2
NetworkFlow1
NoSQL1
OS2
OpenCV1
OpenGL2
Python10
RMQ1
Regional3
Repost1
Ryzen1
SQLserver1
SSL1
System Design1
TOEFL1
Template3
Tree1
Trie2
UEFI4
UX1
Ubuntu14
Unix1
Windows2
Wordpress3
ZFS1
ZOJ1
ajax1
asm1
css1
cuda1
cudnn1
curl1
docker1
es61
font1
ftp1
git1
gitlab1
hardware1
hdu2
hexo1
html1
https1
iOS1
interview1
java1
javascript1
jdk1
jquery1
js7
json1
kext1
macOS2
network1
nginx4
node1
nodejs1
npm1
php8
python1
react2
react native1
regex1
string4
二分图1
二分查找3
博弈1
容斥原理3
并查集1
并行计算1
微积分1
扫描线3
数列1
数独1
数论1
概率2
模拟4
欧拉回路1
百度之星1
知乎1
离散化1
约瑟夫1
线段树3
组合数学1
网络赛2
背包1
背包问题1
转载博文1
递归1

Subscribe for updates

Links

×