3
31
2016
0

[UOJ34] 多项式乘法

第一道FFT

话说后缀数组我只会敲模版……这几天的比赛验证了我连暴力都能写挂

但是最近好像碰到好多FFT题目，于是就学习了一下

?
uoj 34
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
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<cstring>
using namespace std;
 
const double Pi=2*asin(1);
const int NUM_SIZE=100005;
 
int An,Bn,Cn,Rev[NUM_SIZE*3],Step,n;
 
struct Complex{
double a,b;
Complex(double as=0.0,double bs=0.0){a=as;b=bs;}
friend Complex operator+(Complex a,Complex b){return Complex(a.a+b.a,a.b+b.b);}
friend Complex operator-(Complex a,Complex b){return Complex(a.a-b.a,a.b-b.b);}
friend Complex operator*(Complex a,Complex b){return Complex(a.a*b.a-a.b*b.b,b.a*a.b+a.a*b.b);}
friend Complex operator/(Complex a,Complex b){return Complex((a.a*b.a+a.b*b.b)/(b.a*b.a+b.b*b.b),(b.a*a.b-a.a*b.b)/(b.a*b.a+b.b*b.b));}
double Mod(){return sqrt(a*a+b*b);}
}A[NUM_SIZE*3],B[NUM_SIZE*3],C[NUM_SIZE*3];
 
template<typename T>void Read(T &x){
int flag=1;
char ch;
while((ch=getchar())<'0' || ch>'9')if(ch=='-')flag=-1;
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=x*10+ch-'0';
x*=flag;
}
 
void FFT(Complex *x,int flag){
for(int i=0;i<n;i++)if(i<Rev[i])swap(x[i],x[Rev[i]]);
for(int k=1;k<n;k<<=1){
    Complex wk=Complex(cos(Pi/k),flag*sin(Pi/k));
    for(int i=0;i<n;i+=k<<1){
        Complex wkj=Complex(1.0,0.0);
        for(int j=0;j<k;j++){
            Complex a=x[i+j],b=x[i+j+k]*wkj;
            x[i+j]=a+b;
            x[i+j+k]=a-b;
            wkj=wkj*wk;
        }
    }
}
if(flag==-1){for(int i=0;i<n;i++)x[i].a/=n;}
}
 
int main(){
freopen("34.in","r",stdin);
freopen("34.out","w",stdout);
Read(An);Read(Bn);
An++;Bn++;
Cn=An+Bn-1;
for(int i=0;i<An;i++)Read(A[i].a);
for(int i=0;i<Bn;i++)Read(B[i].a);
for(n=1,Step=0;n<Cn;Step++,n<<=1);
for(int i=0;i<n;i++)Rev[i]=(Rev[i>>1]>>1)|((i&1)<<(Step-1));
FFT(A,1);
FFT(B,1);
for(int i=0;i<n;i++)C[i]=A[i]*B[i];
FFT(C,-1);
for(int i=0;i<Cn;i++)printf("%d ",(int)(C[i].a+0.5));
putchar('\n');
return 0;
}
Category: 其他OJ | Tags: OI uoj
3
30
2016
0

[BZOJ3343] 教主的魔法

分块

每个块维护两个数组，一个是按位置排序，另一个按大小排序

修改暴力做两块，中间搞个tag

询问两块暴力，中间二分

?
bzoj 3343
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
#include<cstdio>
#include<algorithm>
using namespace std;
 
int n,q,cnt;
const int block_size=1000,block_num=1000;
 
struct Block{
int block1[block_size+5],block2[block_size+5];
int n,tag;
}block[block_num+5];
 
void Add(int l,int r,int v){
int first_block=(l-1)/block_size+1,last_block=(r-1)/block_size+1,first_pos=(l-1)%block_size+1,last_pos=(r-1)%block_size+1;
if(first_block==last_block){
    for(int i=first_pos;i<=last_pos;i++)block[first_block].block1[i]+=v;
    for(int i=1;i<=block[first_block].n;i++)block[first_block].block2[i]=block[first_block].block1[i];
    sort(block[first_block].block2+1,block[first_block].block2+block[first_block].n+1);
    return;
}
for(int i=first_block+1;i<last_block;i++)block[i].tag+=v;
for(int i=first_pos;i<=block[first_block].n;i++)block[first_block].block1[i]+=v;
for(int i=1;i<=block[first_block].n;i++)block[first_block].block2[i]=block[first_block].block1[i];
sort(block[first_block].block2+1,block[first_block].block2+block[first_block].n+1);
for(int i=1;i<=last_pos;i++)block[last_block].block1[i]+=v;
for(int i=1;i<=block[last_block].n;i++)block[last_block].block2[i]=block[last_block].block1[i];
sort(block[last_block].block2+1,block[last_block].block2+block[last_block].n+1);
}
 
int Div(int id,int k){
int l=1,r=block[id].n,ans=0;
while(l<=r){
    int mid=l+r>>1;
    if(block[id].block2[mid]+block[id].tag<k){l=mid+1;ans=mid;}
    else {r=mid-1;}
}
return block[id].n-ans;
}
 
int Query(int l,int r,int k){
int first_block=(l-1)/block_size+1,last_block=(r-1)/block_size+1,first_pos=(l-1)%block_size+1,last_pos=(r-1)%block_size+1,ans=0;
if(first_block==last_block){
    for(int i=first_pos;i<=last_pos;i++)ans+=(k<=(block[first_block].block1[i]+block[first_block].tag));
    return ans;
}
for(int i=first_block+1;i<last_block;i++)ans+=Div(i,k);
for(int i=first_pos;i<=block[first_block].n;i++)ans+=(k<=(block[first_block].block1[i]+block[first_block].tag));
for(int i=1;i<=last_pos;i++)ans+=(k<=(block[last_block].block1[i]+block[last_block].tag));
return ans;
}
 
int main(){
freopen("3343.in","r",stdin);
freopen("3343.out","w",stdout);
scanf("%d %d",&n,&q);
cnt=(n-1)/block_size+1;
for(int i=1;i<cnt;i++)block[i].n=block_size;
block[cnt].n=(n-1)%block_size+1;
for(int i=1;i<=n;i++){
    int pos_block=(i-1)/block_size+1,pos=(i-1)%block_size+1;
    scanf("%d",&block[pos_block].block1[pos]);
}
for(int i=1;i<=cnt;i++){
    for(int j=1;j<=block[i].n;j++)block[i].block2[j]=block[i].block1[j];
    sort(block[i].block2+1,block[i].block2+block[i].n+1);
}
for(int i=1;i<=q;i++){
    int l,r,v;
    char s[5];
    scanf("%s %d %d %d",s,&l,&r,&v);
    if(s[0]=='M')Add(l,r,v);
    if(s[0]=='A')printf("%d\n",Query(l,r,v));
}
return 0;
}
Category: BZOJ | Tags: OI bzoj
3
30
2016
0

初中OI生涯总结

忍不住感慨一下我初中的OI生涯了。。

回想初中我OI搞的惨不忍睹

当时没有老师，班主任和家长也不太资瓷

所以初一就浪掉了，水平=会写helloworld，当时考虑以后搞一搞高考

初二有了一个OI老师，感觉好一点了

还有教仪站的课，就有了两个OI老师(汪老师和贾老师)

但是当时一周一共就两次课，还有很多人不想学就在写作业讲话干扰别人，环境可谓十分恶劣，想听课也很难听的进去

初二上学期，我经历了一次至关重要的转变

我在某一次汪老师出的模拟赛AK了

而且那次就我一个AK，其他人基本都六七十分

所以我的心态就改变了

然后学习了一些高级算法但是因为文化课问题又停OI了

初三一年全部文化课然后一题没做

到了初三的暑假中考考完后……

发现下一届（就是现在初三）出现了好多大爷！

MedalPluS,ahwhzzt等等一大群神犇，水平不知道比我高到哪里去了

然后就方了，觉得今年被高二碾压，明年被高一碾压

然后进不了省队不就GG了吗

然后开始叹息痛恨于没有老师指点，环境十分恶劣

要是我初中去了27中也许水平就会变高不少？

我的下一届学弟都有了老师和稳定的刷题计划

学习环境也都变好了很多很多，至少会有学长djch等人教你们，上课也不会有一群人自己不听还去干扰你

而初三的我即使保送了FZ，但是还是因为班主任“你要拼中考”而放弃了一年OI，现在当然被虐惨了

wyx大爷初三就去FZ培训了……我还在学校玩泥巴

唉，毕竟都是往事，现在的我要为了明年的省队奋斗

不能被到时候的高一虐惨了然后没进省队就AFO了

总之还是要多做题提高实力啊

自己选择的路，跪着也要走完！

Bless All.

Category: 随笔 | Tags: 随笔 弱
3
29
2016
0

[BZOJ1468] Tree

一模一样的点分治……

为了凑博客数又复制了一遍

?
bzoj 1468
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
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
   
int n,k,h[40005],en,mx[40005],siz[40005],ans,root,val,vis[40005],temp[40005],cnt;
   
struct Edge{
int b,v,next;
}e[80005];
   
void AddEdge(int sa,int sb,int sc){
e[++en].b=sb;
e[en].v=sc;
e[en].next=h[sa];
h[sa]=en;
}
   
void DfsSiz(int u,int fa){
siz[u]=1;
mx[u]=0;
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(v!=fa && !vis[v]){
        DfsSiz(v,u);
        siz[u]+=siz[v];
        mx[u]=max(mx[u],siz[v]);
    }
}
}
   
void DfsRoot(int point,int u,int fa){
mx[u]=max(mx[u],siz[point]-siz[u]);
if(val>mx[u]){val=mx[u];root=u;}
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(v!=fa && !vis[v])DfsRoot(point,v,u);
}
}
   
void GetDist(int u,int fa,int val){
temp[++cnt]=val;
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(v!=fa && !vis[v])GetDist(v,u,val+e[i].v);
}
}
   
int Cal(int u,int val){
cnt=0;
int now=0;
GetDist(u,u,val);
sort(temp+1,temp+cnt+1);
//for(int i=1;i<=cnt;i++)printf("Temp:%d\n",temp[i]);
int i=1,j=cnt;
while(i<j){
    while(temp[i]+temp[j]>k && i<j)j--;
    now+=j-i;
    i++;
}
//printf("Now:%d\n",now);
return now;
}
   
void Dfs(int u){
val=2100000000;
DfsSiz(u,u);
DfsRoot(u,u,0);
ans+=Cal(root,0);
//printf("Ans:%d\n",ans);
vis[root]=1;
for(int i=h[root];i;i=e[i].next){
    int v=e[i].b;
    if(!vis[v]){
        ans-=Cal(v,e[i].v);
        Dfs(v);
    }
}
}
   
int main(){
freopen("1468.in","r",stdin);
freopen("1468.out","w",stdout);
scanf("%d",&n);
//memset(h,0,sizeof(h));
//memset(vis,0,sizeof(vis));
//ans=en=0;
for(int i=1;i<n;i++){
    int sa,sb,sc;
    scanf("%d %d %d",&sa,&sb,&sc);
    AddEdge(sa,sb,sc);
    AddEdge(sb,sa,sc);
}
scanf("%d",&k);
Dfs(1);
printf("%d\n",ans);
return 0;
}
Category: BZOJ | Tags: OI bzoj
3
28
2016
1

[POJ1741] Tree

点分治第一题

这题我们考虑点分治

首先我们需要找到树的重心

然后做一遍

然后分成左右两块继续做，每一块重复上面的操作

具体的，我们每次计算每个点到重心的距离

然后放到一个数组里，再将距离和小于k的算进去

但是有可能重复统计了子树里面的数值

所以点分治的时候再减一下就好了

?
poj 1741
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
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
 
int n,k,h[10005],en,mx[10005],siz[10005],ans,root,val,vis[10005],temp[10005],cnt;
 
struct Edge{
int b,v,next;
}e[20005];
 
void AddEdge(int sa,int sb,int sc){
e[++en].b=sb;
e[en].v=sc;
e[en].next=h[sa];
h[sa]=en;
}
 
void DfsSiz(int u,int fa){
siz[u]=1;
mx[u]=0;
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(v!=fa && !vis[v]){
        DfsSiz(v,u);
        siz[u]+=siz[v];
        mx[u]=max(mx[u],siz[v]);
    }
}
}
 
void DfsRoot(int point,int u,int fa){
mx[u]=max(mx[u],siz[point]-siz[u]);
if(val>mx[u]){val=mx[u];root=u;}
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(v!=fa && !vis[v])DfsRoot(point,v,u);
}
}
 
void GetDist(int u,int fa,int val){
temp[++cnt]=val;
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(v!=fa && !vis[v])GetDist(v,u,val+e[i].v);
}
}
 
int Cal(int u,int val){
cnt=0;
int now=0;
GetDist(u,u,val);
sort(temp+1,temp+cnt+1);
int i=1,j=cnt;
while(i<j){
    while(temp[i]+temp[j]>k && i<j)j--;
    now+=j-i;
    i++;
}
return now;
}
 
void Dfs(int u){
val=2100000000;
DfsSiz(u,u);
DfsRoot(u,u,0);
ans+=Cal(root,0);
vis[root]=1;
for(int i=h[root];i;i=e[i].next){
    int v=e[i].b;
    if(!vis[v]){
        ans-=Cal(v,e[i].v);
        Dfs(v);
    }
}
}
 
int main(){
freopen("1741.in","r",stdin);
freopen("1741.out","w",stdout);
while(scanf("%d %d",&n,&k),n|k){
    memset(h,0,sizeof(h));
    memset(vis,0,sizeof(vis));
    ans=en=0;
    for(int i=1;i<n;i++){
        int sa,sb,sc;
        scanf("%d %d %d",&sa,&sb,&sc);
        AddEdge(sa,sb,sc);
        AddEdge(sb,sa,sc);
    }
    Dfs(1);
    printf("%d\n",ans);
}
return 0;
}
Category: 其他OJ | Tags: OI poj
3
27
2016
0

[BZOJ2296] 【POJ Challenge】随机种子

随便构造一下

?
bzoj 2296
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<cstdio>
   
int main(){
freopen("2296.in","r",stdin);
freopen("2296.out","w",stdout);
long long a;
int t;
scanf("%d",&t);
while(t--){
scanf("%lld",&a);
if(a==0){puts("-1");continue;}
printf("%lld\n",1234567890ll*1000000ll+a-(1234567890ll*1000000ll)%a);
}
return 0;
}
Category: BZOJ | Tags: OI bzoj
3
27
2016
0

[BZOJ1565] [NOI2009]植物大战僵尸

拓扑排序消圈+最大权闭合子图

因为每次僵尸都是从右往左走，那么我们对于右往左依次连边

然后每个点的攻击集合就是相当于选了攻击集合中的点就必须选择这个点。

那么我们反向建边，因为有可能出现循环保护的情况，所以先拓扑排序消圈然后按照最大权闭合子图的模型建网络流图即可。

?
bzoj 1565
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
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
 
int en,en1,n,m,ok[1005],cur[1005],h[1005],h1[1005],score[1005],du[1005],level[1005],S,T,now,mxval;
 
struct Edge{
int b,f,next,back;
}e[1000005],e1[1000005];
 
int Cal(int x,int y){return (x-1)*m+y;}
 
void AddEdge1(int sa,int sb){
e1[++en1].b=sb;
e1[en1].next=h1[sa];
h1[sa]=en1;
du[sb]++;
}
 
void AddEdge(int sa,int sb,int sc){
e[++en].b=sb;
e[en].back=en+1;
e[en].f=sc;
e[en].next=h[sa];
h[sa]=en;
swap(sa,sb);
e[++en].b=sb;
e[en].back=en-1;
e[en].f=0;
e[en].next=h[sa];
h[sa]=en;
}
 
int BFS(){
queue<int> Q;
Q.push(S);
memset(level,0,sizeof(level));
level[S]=1;
while(!Q.empty()){
    int u=Q.front();
    Q.pop();
    for(int i=h[u];i;i=e[i].next){
        int v=e[i].b;
        if(level[v] || !e[i].f)continue;
        Q.push(v);
        level[v]=level[u]+1;
    }
}
return level[T];
}
 
int DFS(int u,int flow){
if(u==T)return flow;
int f=flow;
for(int &i=cur[u];i;i=e[i].next){
    int v=e[i].b,fl;
    if(level[v]==level[u]+1 && e[i].f && (fl=DFS(v,min(f,e[i].f)))){
        f-=fl;
        e[i].f-=fl;
        e[e[i].back].f+=fl;
        if(!f)return flow;
    }
}
return flow-f;
}
 
int Dinic(){
int ans=0;
while(BFS()){
    for(int i=1;i<=T;i++)cur[i]=h[i];
    ans+=DFS(S,2100000000);
}
return ans;
}
 
void Toposort(){
queue<int> Q;
for(int i=1;i<=now;i++){
    if(!du[i]){ok[i]=1;Q.push(i);}
}
while(!Q.empty()){
    int u=Q.front();
    Q.pop();
    for(int i=h1[u];i;i=e1[i].next){
        int v=e1[i].b;
        du[v]--;
        if(!du[v]){ok[v]=1;Q.push(v);}
    }
}
}
 
int main(){
freopen("1565.in","r",stdin);
freopen("1565.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        int can;
        now++;
        scanf("%d %d",&score[now],&can);
        for(int k=1;k<=can;k++){
            int dx,dy;
            scanf("%d %d",&dx,&dy);
            dx++;dy++;
            AddEdge1(now,Cal(dx,dy));
        }
        if(j!=m)AddEdge1(now+1,now);
    }
}
Toposort();
S=now+1;T=now+2;
for(int i=1;i<=now;i++){
    if(ok[i]){
        if(score[i]>=0){AddEdge(S,i,score[i]);mxval+=score[i];}
        else AddEdge(i,T,-score[i]);
        for(int j=h1[i];j;j=e1[j].next){
            int v=e1[j].b;
            if(ok[v])AddEdge(v,i,2100000000);
        }
    }
}
printf("%d\n",mxval-Dinic());
return 0;
}
Category: BZOJ | Tags: OI bzoj
3
26
2016
0

[BZOJ4423] [AMPPZ2013]Bytehattan

很久以前wzf出给我们的题目。。。

考虑加边，每次并查集加完只要并查集内联通就说明实际堵塞

不联通就说明实际联通

?
bzoj 4423
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
#include<cstdio>
    
int n,k,ans=1,f[10000005];
    
int Find(int x){
return x==f[x]?f[x]:f[x]=Find(f[x]);
}
    
void Union(int sa,int sb){
if(sa>sb)f[sa]=sb;
else f[sb]=sa;
}
    
int Get(int x,int y){
if(x==n || y==n || x==0 || y==0)return 0;
return (x-1)*n+y;
}
    
int main(){
freopen("4423.in","r",stdin);
freopen("4423.out","w",stdout);
scanf("%d %d",&n,&k);
for(int i=1;i<=n*n+n;i++)f[i]=i;
while(k--){
    int sa1,sb1,sa2,sb2;
    char w1[5],w2[5];
    scanf("%d %d %s %d %d %s",&sa1,&sb1,w1,&sa2,&sb2,w2);
    if(ans==0){sa1=sa2;sb1=sb2;w1[0]=w2[0];}
    if(w1[0]=='N'){
        if(Find(Get(sa1,sb1))!=Find(Get(sa1-1,sb1))){Union(Find(Get(sa1,sb1)),Find(Get(sa1-1,sb1)));ans=1;}
        else ans=0;
    }
    else {
        if(Find(Get(sa1,sb1))!=Find(Get(sa1,sb1-1))){Union(Find(Get(sa1,sb1)),Find(Get(sa1,sb1-1)));ans=1;}
        else ans=0;
    }
    if(ans)puts("TAK");
    else puts("NIE");
}
return 0;
}
Category: BZOJ | Tags: OI bzoj
3
23
2016
0

[BZOJ2705] [SDOI2012]Longge的问题

sb题写挂还有资格参加省选？

写挂10+次，莫名RE，简直崩溃

最后选择了抄hzwer的代码

这题是一个裸的欧拉函数

把原题中的式子拆一下就行了

?
bzoj 2705
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
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
long long n,ans=0;
 
long long phiQ(long long x)
{
    long long t=x;
    for(long long i=2;i*i<=n;i++)
        if(x%i==0)
        {
            t=t/i*(i-1);
            while(x%i==0)x/=i;
        }
    if(x>1)t=t/x*(x-1);
    return t;
}
 
int main(){
freopen("2705.in","r",stdin);
freopen("2705.out","w",stdout);
scanf("%lld",&n);
for(long long i=1;i*i<=n;i++){
    if(n%i==0){
        ans+=(long long)i*phiQ(n/i);
        if(i*i<n)ans+=(long long)(n/i)*phiQ(i);
    }
}
printf("%lld\n",ans);
return 0;
}
Category: BZOJ | Tags: OI bzoj
3
23
2016
0

[BZOJ4443] [Scoi2015]小凸玩矩阵

二分判定,使用网络流

暴力重构图即可

?
bzoj 4443
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
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
 
int n,m,k,en,h[705],level[705],S,T,cur[705],scr[255][255];
 
struct Edge{
int b,next,f,back;
}e[1000005];
 
void AddEdge(int sa,int sb,int sc){
e[++en].b=sb;
e[en].f=sc;
e[en].back=en+1;
e[en].next=h[sa];
h[sa]=en;
swap(sa,sb);
e[++en].b=sb;
e[en].f=0;
e[en].back=en-1;
e[en].next=h[sa];
h[sa]=en;
}
 
int Bfs(){
queue<int> Q;
memset(level,0,sizeof(level));
level[S]=1;
Q.push(S);
while(!Q.empty()){
    int u=Q.front();
    Q.pop();
    for(int i=h[u];i;i=e[i].next){
        int v=e[i].b;
        if(!e[i].f || level[v])continue;
        level[v]=level[u]+1;
        Q.push(v);
    }
}
return level[T];
}
 
int Dfs(int u,int flow){
if(u==T)return flow;
int f=flow;
for(int &i=cur[u];i;i=e[i].next){
    int v=e[i].b,fl;
    if(e[i].f && level[v]==level[u]+1 && (fl=Dfs(v,min(f,e[i].f)))){
        f-=fl;
        e[i].f-=fl;
        e[e[i].back].f+=fl;
        if(f==0)return flow;
    }
}
return flow-f;
}
 
int Dinic(){
int ans=0;
while(Bfs()){for(int i=1;i<=T;i++)cur[i]=h[i];ans+=Dfs(S,2100000000);}
return ans;
}
 
int Check(int score){
memset(h,0,sizeof(h));
en=0;
for(int i=1;i<=n;i++)AddEdge(S,i,1);
for(int i=1;i<=m;i++)AddEdge(i+n,T,1);
for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        if(scr[i][j]<=score)AddEdge(i,j+n,1);
    }
}
return Dinic()>n-k;
}
 
int main(){
freopen("4443.in","r",stdin);
freopen("4443.out","w",stdout);
scanf("%d %d %d",&n,&m,&k);
for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        scanf("%d",&scr[i][j]);
    }
}
S=n+m+1;
T=n+m+2;
int l=1,r=100000000,ans=0;
while(l<=r){
    int mid=l+r>>1;
    if(Check(mid)){ans=mid;r=mid-1;}
    else {l=mid+1;}
}
printf("%d\n",ans);
return 0;
}
Category: BZOJ | Tags: OI bzoj

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com