BestCoder #1

正文索引 [隐藏]

A.逃生
题解
B.项目管理
题解
C.海岸线
题解

A.逃生

http://acm.hdu.edu.cn/showproblem.php?pid=4857

题解

这到题目直接拓扑排序就可以了。

//WNJXYK
//while(true) RP++;
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<string>
#include<cstring>
using namespace std;
const int Maxn=30010;
const int Maxm=100010;
int T;
int n,m;
priority_queue<int> que;
struct Edge{
    int v,nxt;
    Edge(){}
    Edge(int v0,int n0){
        v=v0;
        nxt=n0;
    }
};
Edge e[Maxm];
int head[Maxn];
int nume;
inline void addEdge(int u,int v){
    e[++nume]=Edge(v,head[u]);
    head[u]=nume;
}
int Ans[Maxn];
int top;
int inner[Maxn];
inline void solve(){
    scanf("%d%d",&n,&m);
    memset(inner,0,sizeof(inner));
    memset(head,0,sizeof(head));
    nume=0;
    while(!que.empty()) que.pop();
    top=0;
    for (int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        inner[x]++;
        addEdge(y,x);
    }
    for (int i=1;i<=n;i++) if (!inner[i]) que.push(i);
    while(!que.empty()){
        int now=que.top();
        que.pop();
        for (int i=head[now];i;i=e[i].nxt){
            int v=e[i].v;
            inner[v]--;
            if (!inner[v])
                que.push(v);
        }
        Ans[++top]=now;
    }
    for (int i=n;i>1;i--)
        printf("%d ",Ans[i]);
    printf("%d\n",Ans[1]);
}
int main(){
    scanf("%d",&T);
    for (;T--;) solve();
    return 0;
}

//WNJXYK

//while(true) RP++;

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<map>

#include<set>

#include<queue>

#include<string>

#include<cstring>

using namespace std;

const int Maxn=30010;

const int Maxm=100010;

int T;

int n,m;

priority_queue<int> que;

struct Edge{

int v,nxt;

Edge(){}

Edge(int v0,int n0){

v=v0;

nxt=n0;

}

};

Edge e[Maxm];

int head[Maxn];

int nume;

inline void addEdge(int u,int v){

e[++nume]=Edge(v,head[u]);

head[u]=nume;

}

int Ans[Maxn];

int top;

int inner[Maxn];

inline void solve(){

scanf("%d%d",&n,&m);

memset(inner,0,sizeof(inner));

memset(head,0,sizeof(head));

nume=0;

while(!que.empty()) que.pop();

top=0;

for (int i=1;i<=m;i++){

int x,y;

scanf("%d%d",&x,&y);

inner[x]++;

addEdge(y,x);

}

for (int i=1;i<=n;i++) if (!inner[i]) que.push(i);

while(!que.empty()){

int now=que.top();

que.pop();

for (int i=head[now];i;i=e[i].nxt){

int v=e[i].v;

inner[v]--;

if (!inner[v])

que.push(v);

}

Ans[++top]=now;

}

for (int i=n;i>1;i--)

printf("%d ",Ans[i]);

printf("%d\n",Ans[1]);

}

int main(){

scanf("%d",&T);

for (;T--;) solve();

return 0;

}

B.项目管理

http://acm.hdu.edu.cn/showproblem.php?pid=4858

题解

算法复合。。。对于连有>Sqrt(n)条边的点最多不超过Sqrt(n)个,这些点的答案,我们在计算的时候暴力加起来.连有<Sqtn(n)条边的点我们在增加对应值的时候直接加到它周围的节点.这样两个操作全都是O(Sqtn(n))的复杂的.

//WNJXYK
//while(true) RP++;
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<string>
#include<cstring>
#include<cmath>
using namespace std;
const int Maxn=100010;
const int Maxm=100020;
struct Link{
    int x,y;
};
Link link[Maxm];
struct Edge{
    int v,nxt;
    Edge(){}
    Edge(int v0,int n0){
        v=v0;
        nxt=n0;
    }
};
Edge e[Maxm*4];
int head[Maxn];
int big[Maxn];
//int small[Maxn];
int nume;
int cnt[Maxn];
int val[Maxn],eng[Maxn];
inline void addEdge(int u,int v){
    e[++nume]=Edge(v,head[u]);
    head[u]=nume;
}
inline void addBig(int u,int v){
    e[++nume]=Edge(v,big[u]);
    big[u]=nume;
}
/*
inline void addSmall(int u,int v){
    e[++nume]=Edge(v,small[u]);
    small[u]=nume;
}*/
int Q;
int n,m;
int sqtn;
inline void solve(){
    memset(head,0,sizeof(head));
    memset(big,0,sizeof(big));
    memset(val,0,sizeof(val));
    memset(eng,0,sizeof(eng));
    nume=0;
    scanf("%d%d",&n,&m);
    sqtn=sqrt(n);
    for (int i=1;i<=m;i++){
        scanf("%d%d",&link[i].x,&link[i].y);
        cnt[link[i].x]++;
        cnt[link[i].y]++;
    }
    for (int i=1;i<=m;i++){
        addEdge(link[i].x,link[i].y);addEdge(link[i].y,link[i].x);
        if (cnt[link[i].y]>sqtn) addBig(link[i].x,link[i].y); //else addSmall(link[i].x,link[i].y);
        if (cnt[link[i].x]>sqtn) addBig(link[i].y,link[i].x); //else addSmall(link[i].y,link[i].x);
    }
    scanf("%d",&Q);
    for (int i=1;i<=Q;i++){
        int cmd,u,v;
        scanf("%d",&cmd);
        if (cmd==0){
            scanf("%d%d",&u,&v);
            if (cnt[u]>sqtn)
                eng[u]+=v;
            else
                for (int i=head[u];i;i=e[i].nxt) val[e[i].v]+=v;
        }else{
            scanf("%d",&u);
            int ret=val[u];
            for (int i=big[u];i;i=e[i].nxt) ret+=eng[e[i].v];
            printf("%d\n",ret);
        }
    }
}
int T;
int main(){
    scanf("%d",&T);
    for (;T--;) solve();
}

//WNJXYK

//while(true) RP++;

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<map>

#include<set>

#include<queue>

#include<string>

#include<cstring>

#include<cmath>

using namespace std;

const int Maxn=100010;

const int Maxm=100020;

struct Link{

int x,y;

};

Link link[Maxm];

struct Edge{

int v,nxt;

Edge(){}

Edge(int v0,int n0){

v=v0;

nxt=n0;

}

};

Edge e[Maxm*4];

int head[Maxn];

int big[Maxn];

//int small[Maxn];

int nume;

int cnt[Maxn];

int val[Maxn],eng[Maxn];

inline void addEdge(int u,int v){

e[++nume]=Edge(v,head[u]);

head[u]=nume;

}

inline void addBig(int u,int v){

e[++nume]=Edge(v,big[u]);

big[u]=nume;

}

inline void addSmall(int u,int v){

e[++nume]=Edge(v,small[u]);

small[u]=nume;

}*/

int Q;

int n,m;

int sqtn;

inline void solve(){

memset(head,0,sizeof(head));

memset(big,0,sizeof(big));

memset(val,0,sizeof(val));

memset(eng,0,sizeof(eng));

nume=0;

scanf("%d%d",&n,&m);

sqtn=sqrt(n);

for (int i=1;i<=m;i++){

scanf("%d%d",&link[i].x,&link[i].y);

cnt[link[i].x]++;

cnt[link[i].y]++;

}

for (int i=1;i<=m;i++){

addEdge(link[i].x,link[i].y);addEdge(link[i].y,link[i].x);

if (cnt[link[i].y]>sqtn) addBig(link[i].x,link[i].y); //else addSmall(link[i].x,link[i].y);

if (cnt[link[i].x]>sqtn) addBig(link[i].y,link[i].x); //else addSmall(link[i].y,link[i].x);

}

scanf("%d",&Q);

for (int i=1;i<=Q;i++){

int cmd,u,v;

scanf("%d",&cmd);

if (cmd==0){

scanf("%d%d",&u,&v);

if (cnt[u]>sqtn)

eng[u]+=v;

else

for (int i=head[u];i;i=e[i].nxt) val[e[i].v]+=v;

}else{

scanf("%d",&u);

int ret=val[u];

for (int i=big[u];i;i=e[i].nxt) ret+=eng[e[i].v];

printf("%d\n",ret);

}

int T;

int main(){

scanf("%d",&T);

for (;T--;) solve();

}

C.海岸线

http://acm.hdu.edu.cn/showproblem.php?pid=4859

题解

黑白染色+最小割（我的裸的Dinic又被卡了、、似乎需要一些优化、、

//WNJXYK
//while(true) RP++;
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<string>
#include<cstring>
using namespace std;
const int Maxn=2510;
const int Maxm=Maxn*10;
const int Inf=2100000000;
struct Edge{
    int v,nxt,f;
    Edge(){}
    Edge(int v0,int n0,int f0){
        v=v0;
        nxt=n0;
        f=f0;
    }
};
Edge e[Maxm*2];
int head[Maxn];
int nume;
inline void addEdge(int u,int v,int f){
    e[++nume]=Edge(v,head[u],f);
    head[u]=nume;
    e[++nume]=Edge(u,head[v],0);
    head[v]=nume;
}
inline void addOneEdge(int u,int v,int f){
    e[++nume]=Edge(v,head[u],f);
    head[u]=nume;
}
int sink,src;
queue<int> que;
int dist[Maxn];
inline int remin(int a,int b){
    if (a<b) return a;
    return b;
}
inline bool spfa(){
    while(!que.empty()) que.pop();
    memset(dist,-1,sizeof(dist));
    dist[src]=0;
    que.push(src);
    while(!que.empty()){
        int now=que.front();
        que.pop();
        for (int i=head[now];i;i=e[i].nxt){
            int v=e[i].v;
            if (e[i].f>0 && dist[v]==-1){
                dist[v]=dist[now]+1;
                que.push(v);
            }
        }
    }
    if (dist[sink]==-1) return false;
    return true;
}
int dfs(int x,int delta){
    if (x==sink){
        return delta;
    }else{
        int ret=0;
        for (int i=head[x];i;i=e[i].nxt){
            int v=e[i].v;
            if (e[i].f>0 && dist[v]==dist[x]+1){
                int ddelta=dfs(v,remin(e[i].f,delta));
                e[i].f-=ddelta;
                e[i^1].f+=ddelta;
                ret+=ddelta;
                delta-=ddelta;
                if (delta==0) break;
            }
        }
        if (!ret) dist[x]=-1;
        return ret;
    }
}
inline int dinic(){
    int ret=0;
    while(spfa()) ret+=dfs(src,Inf);
    return ret;
}
int n,m;
int isLand[55][55];
int Sum=0,Wall=0;
inline void init(){
    nume=1;
    memset(head,0,sizeof(head));
    memset(isLand,0,sizeof(isLand));
    Sum=0;Wall=0;
}
inline char readChar(){
    char x=getchar();
    while(!(x=='D' || x=='E' || x=='.')) x=getchar();
    return x;
}
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
inline void solve(){
    init();
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){
            char x=readChar();
            if (x=='E') isLand[i+1][j+1]=1;
            if (x=='D') isLand[i+1][j+1]=0;
            if (x=='.') isLand[i+1][j+1]=2;
        }
    }
    n+=2;m+=2;
    /*for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){
            if (isLand[i][j]==1) printf("E");
            if (isLand[i][j]==0) printf("D");
            if (isLand[i][j]==2) printf(".");
        }
        printf("\n");
    }*/
    src=n*m+1;sink=n*m+2;
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){
            Sum++;
            if ((i+j)%2){
                switch(isLand[i][j]){
                    case 1:
                        addEdge(src,(i-1)*m+j,1);
                        addEdge((i-1)*m+j,sink,1);
                        for (int k=0;k<4;k++){
                            int x=i+dx[k],y=j+dy[k];
                            if (1<=x && x<=n && 1<=y && y<=m){
                                Wall++;
                                addOneEdge((i-1)*m+j,(x-1)*m+y,1);
                                addOneEdge((x-1)*m+y,(i-1)*m+j,1);
                            }
                        }
                        break;
                    case 0:
                        addEdge(src,(i-1)*m+j,Inf);
                        addEdge((i-1)*m+j,sink,1);
                        for (int k=0;k<4;k++){
                            int x=i+dx[k],y=j+dy[k];
                            if (1<=x && x<=n && 1<=y && y<=m){
                                Wall++;
                                addOneEdge((i-1)*m+j,(x-1)*m+y,1);
                                addOneEdge((x-1)*m+y,(i-1)*m+j,1);
                            }
                        }
                        break;
                    case 2:
                        addEdge(src,(i-1)*m+j,1);
                        addEdge((i-1)*m+j,sink,Inf);
                        for (int k=0;k<4;k++){
                            int x=i+dx[k],y=j+dy[k];
                            if (1<=x && x<=n && 1<=y && y<=m){
                                Wall++;
                                addOneEdge((i-1)*m+j,(x-1)*m+y,1);
                                addOneEdge((x-1)*m+y,(i-1)*m+j,1);
                            }
                        }
                        break;
                }
            }else{
                switch(isLand[i][j]){
                    case 1:
                        addEdge(src,(i-1)*m+j,1);
                        addEdge((i-1)*m+j,sink,1);
                        /*for (int k=0;k<4;k++){
                            int x=i+dx[k],y=j+dy[k];
                            if (1<=x && x<=n && 1<=y && y<=m){
                                Wall++;
                                addOneEdge((i-1)*m+j,(x-1)*m+y,1);
                                addOneEdge((x-1)*m+y,(i-1)*m+j,1);
                            }
                        }*/
                        break;
                    case 0:
                        addEdge(src,(i-1)*m+j,1);
                        addEdge((i-1)*m+j,sink,Inf);
                        /*for (int k=0;k<4;k++){
                            int x=i+dx[k],y=j+dy[k];
                            if (1<=x && x<=n && 1<=y && y<=m){
                                Wall++;
                                addOneEdge((i-1)*m+j,(x-1)*m+y,1);
                                addOneEdge((x-1)*m+y,(i-1)*m+j,1);
                            }
                        }*/
                        break;
                    case 2:
                        addEdge(src,(i-1)*m+j,Inf);
                        addEdge((i-1)*m+j,sink,1);
                        /*for (int k=0;k<4;k++){
                            int x=i+dx[k],y=j+dy[k];
                            if (1<=x && x<=n && 1<=y && y<=m){
                                Wall++;
                                addOneEdge((i-1)*m+j,(x-1)*m+y,1);
                                addOneEdge((x-1)*m+y,(i-1)*m+j,1);
                            }
                        }*/
                        break;
                }
            }
        }
    }
    printf("%d\n",Sum+Wall-dinic());
}
int T;
int main(){
    scanf("%d",&T);
    for (int RT=1;RT<=T;RT++){
        printf("Case %d: ",RT);
        init();
        solve();
    }
    return 0;
}

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

//WNJXYK

//while(true) RP++;

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<map>

#include<set>

#include<queue>

#include<string>

#include<cstring>

using namespace std;

const int Maxn=2510;

const int Maxm=Maxn*10;

const int Inf=2100000000;

struct Edge{

int v,nxt,f;

Edge(){}

Edge(int v0,int n0,int f0){

v=v0;

nxt=n0;

f=f0;

}

};

Edge e[Maxm*2];

int head[Maxn];

int nume;

inline void addEdge(int u,int v,int f){

e[++nume]=Edge(v,head[u],f);

head[u]=nume;

e[++nume]=Edge(u,head[v],0);

head[v]=nume;

}

inline void addOneEdge(int u,int v,int f){

e[++nume]=Edge(v,head[u],f);

head[u]=nume;

}

int sink,src;

queue<int> que;

int dist[Maxn];

inline int remin(int a,int b){

if (a<b) return a;

return b;

}

inline bool spfa(){

while(!que.empty()) que.pop();

memset(dist,-1,sizeof(dist));

dist[src]=0;

que.push(src);

while(!que.empty()){

int now=que.front();

que.pop();

for (int i=head[now];i;i=e[i].nxt){

int v=e[i].v;

if (e[i].f>0 && dist[v]==-1){

dist[v]=dist[now]+1;

que.push(v);

}

if (dist[sink]==-1) return false;

return true;

}

int dfs(int x,int delta){

if (x==sink){

return delta;

}else{

int ret=0;

for (int i=head[x];i;i=e[i].nxt){

int v=e[i].v;

if (e[i].f>0 && dist[v]==dist[x]+1){

int ddelta=dfs(v,remin(e[i].f,delta));

e[i].f-=ddelta;

e[i^1].f+=ddelta;

ret+=ddelta;

delta-=ddelta;

if (delta==0) break;

}

if (!ret) dist[x]=-1;

return ret;

}

inline int dinic(){

int ret=0;

while(spfa()) ret+=dfs(src,Inf);

return ret;

}

int n,m;

int isLand[55][55];

int Sum=0,Wall=0;

inline void init(){

nume=1;

memset(head,0,sizeof(head));

memset(isLand,0,sizeof(isLand));

Sum=0;Wall=0;

}

inline char readChar(){

char x=getchar();

while(!(x=='D' || x=='E' || x=='.')) x=getchar();

return x;

}

int dx[]={1,0,-1,0};

int dy[]={0,1,0,-1};

inline void solve(){

init();

scanf("%d%d",&n,&m);

for (int i=1;i<=n;i++){

for (int j=1;j<=m;j++){

char x=readChar();

if (x=='E') isLand[i+1][j+1]=1;

if (x=='D') isLand[i+1][j+1]=0;

if (x=='.') isLand[i+1][j+1]=2;

}

n+=2;m+=2;

/*for (int i=1;i<=n;i++){

for (int j=1;j<=m;j++){

if (isLand[i][j]==1) printf("E");

if (isLand[i][j]==0) printf("D");

if (isLand[i][j]==2) printf(".");

}

printf("\n");

}*/

src=n*m+1;sink=n*m+2;

for (int i=1;i<=n;i++){

for (int j=1;j<=m;j++){

Sum++;

if ((i+j)%2){

switch(isLand[i][j]){

case 1:

addEdge(src,(i-1)*m+j,1);

addEdge((i-1)*m+j,sink,1);

for (int k=0;k<4;k++){

int x=i+dx[k],y=j+dy[k];

if (1<=x && x<=n && 1<=y && y<=m){

Wall++;

addOneEdge((i-1)*m+j,(x-1)*m+y,1);

addOneEdge((x-1)*m+y,(i-1)*m+j,1);

}

break;

case 0:

addEdge(src,(i-1)*m+j,Inf);

addEdge((i-1)*m+j,sink,1);

for (int k=0;k<4;k++){

int x=i+dx[k],y=j+dy[k];

if (1<=x && x<=n && 1<=y && y<=m){

Wall++;

addOneEdge((i-1)*m+j,(x-1)*m+y,1);

addOneEdge((x-1)*m+y,(i-1)*m+j,1);

}

break;

case 2:

addEdge(src,(i-1)*m+j,1);

addEdge((i-1)*m+j,sink,Inf);

for (int k=0;k<4;k++){

int x=i+dx[k],y=j+dy[k];

if (1<=x && x<=n && 1<=y && y<=m){

Wall++;

addOneEdge((i-1)*m+j,(x-1)*m+y,1);

addOneEdge((x-1)*m+y,(i-1)*m+j,1);

}

break;

}

}else{

switch(isLand[i][j]){

case 1:

addEdge(src,(i-1)*m+j,1);

addEdge((i-1)*m+j,sink,1);

/*for (int k=0;k<4;k++){

int x=i+dx[k],y=j+dy[k];

if (1<=x && x<=n && 1<=y && y<=m){

Wall++;

addOneEdge((i-1)*m+j,(x-1)*m+y,1);

addOneEdge((x-1)*m+y,(i-1)*m+j,1);

}

}*/

break;

case 0:

addEdge(src,(i-1)*m+j,1);

addEdge((i-1)*m+j,sink,Inf);

/*for (int k=0;k<4;k++){

int x=i+dx[k],y=j+dy[k];

if (1<=x && x<=n && 1<=y && y<=m){

Wall++;

addOneEdge((i-1)*m+j,(x-1)*m+y,1);

addOneEdge((x-1)*m+y,(i-1)*m+j,1);

}

}*/

break;

case 2:

addEdge(src,(i-1)*m+j,Inf);

addEdge((i-1)*m+j,sink,1);

/*for (int k=0;k<4;k++){

int x=i+dx[k],y=j+dy[k];

if (1<=x && x<=n && 1<=y && y<=m){

Wall++;

addOneEdge((i-1)*m+j,(x-1)*m+y,1);

addOneEdge((x-1)*m+y,(i-1)*m+j,1);

}

}*/

break;

}

printf("%d\n",Sum+Wall-dinic());

}

int T;

int main(){

scanf("%d",&T);

for (int RT=1;RT<=T;RT++){

printf("Case %d: ",RT);

init();

solve();

}

return 0;

}

WNJXYKの博客

喂你脚下有坑

BestCoder #1

A.逃生

题解

B.项目管理

题解

C.海岸线

题解

扫一扫支付

评论放弃治疗

创作日历

文章

标签云

最近访客

2022年 5月
一	二	三	四	五	六	日
						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

BestCoder #1

A.逃生

题解

B.项目管理

题解

C.海岸线

题解

扫一扫支付

评论 放弃治疗

评论放弃治疗