BZOJ1834

@OceanEye7年前

04/8

00:03

嘛……几万年没好好写过网络流了……
gap优化真的强，把我的1s的代码降成了0.05s
相信前面榜上的就是gap的吧……

/**************************************************************
    Problem: 1834
    User: OceanEYe
    Language: C++
    Result: Accepted
    Time:56 ms
    Memory:1948 kb
****************************************************************/
 
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <queue>
#include <set>
#define p(x) ('0'<=x&&x<='9')
#define INF 100000000
char cc; int C;
template <class T>
void read(T &x)
{
    cc=getchar(); C=1; x=0;
    while(!p(cc))
    {
        if(cc=='-') C=-1;
        cc=getchar();
    }
    while(p(cc)) x=x*10+cc-48,cc=getchar();
    x*=C;
}
template <class T>
void MN(T &x,T y) { x>y?x=y:x=x; }
 
using namespace std;
#define N 1005
#define E 10010
 
struct Tedge
{
    int from,to,cap,flow;
    int val;
}edge[E<<2];
#define TO edge[i].to
#define VAL edge[i].val
#define SIZ (edge[i].cap-edge[i].flow)
#define CAP edge[i].cap
int fst[N],NXT[E<<2],e_tot;
void add_e(int _,int __,int ___,int ____)
{
    edge[e_tot].to=__; edge[e_tot].cap=___; edge[e_tot].from=_; edge[e_tot].val=____;
    NXT[e_tot]=fst[_]; fst[_]=e_tot++;
    edge[e_tot].to=_; edge[e_tot].cap=___; edge[e_tot].flow=___; edge[e_tot].from=__; edge[e_tot].val=-____;
    NXT[e_tot]=fst[__]; fst[__]=e_tot++;
}
 
int S,T;
struct rec
{
    int a,b,c,d;
    rec(int _,int __,int ___,int ____): a(_),b(__),c(___),d(____) {}
};
 
vector <rec> R; 
int n,m,k;
void init1()
{
    read(n); read(m); read(k);
    S=1; T=n;
    int _,__,___,____;
    memset(fst,-1,sizeof(fst));
    for(int i=1;i<=m;i++)
    {
        read(_); read(__); read(___); read(____);
        add_e(_,__,___,0);
        R.push_back(rec(_,__,___,____));
    }
}
//
bool vis[N];
int d[N],cnt[N],p[N],pre[N],ans;
int Augment()
{
    int r=T,c=INF,i;
    while(r!=S)
    {
        i=pre[r];
        MN(c,CAP-SIZ);
        r=TO;
    }
    r=T;
    while(r!=S)
    {
        i=pre[r];
        edge[i].flow-=c; edge[i^1].flow+=c;
        r=TO;
    }
    return c;
}
void ISAP()
{
    int node=S,c;
    for(int i=1;i<=n;i++) p[i]=fst[i];
    bool flag;
    while(d[S]<=n)
    {
        if(node==T)
        {
            ans+=Augment();
            node=S;
        }
        //solve
        flag=false;
        for(int i=p[node];~i;i=NXT[i])
        {
            if(d[TO]!=d[node]-1||SIZ==0) continue;
            p[node]=i;
            pre[TO]=i^1;
            node=TO;
            flag=true;
            break;
        }
        if(flag) continue;
        c=n+10;
        for(int i=fst[node];~i;i=NXT[i])
        {
            if(!SIZ) continue;
            MN(c,d[TO]+1);
        }
        if(--cnt[d[node]]==0)
        {
            printf("%d ",ans);
            return;
        }
        cnt[d[node]=c]++;
        p[node]=fst[node];
        if(node!=S)node=edge[pre[node]].to;
        //retreat
    }
    printf("%d ",ans);
}
queue<int> Q;
void bfs()
{
    int x;
    memset(vis,0,sizeof(vis));
    d[T]=1; Q.push(T); vis[T]^=1;
    while(!Q.empty())
    {
        x=Q.front(); Q.pop(); 
        cnt[d[x]]++;
        for(int i=fst[x];~i;i=NXT[i])
        {
            if(vis[TO]||SIZ) continue;
            d[TO]=d[x]+1;
            Q.push(TO);
            vis[TO]^=1;
        }
    }
}
//
int dis[N],cost;
void init2()
{
    int _,__,___,____;
    for(int i=0;i<m;i++)
    {
        _=R[i].a;
        __=R[i].b;
        ____=R[i].d;
        add_e(_,__,INF,____);
    }
}
int Augment2()
{
    int r=T,c=0,i;
    while(r!=S)
    {
        i=pre[r];
        edge[i].flow--; edge[i^1].flow++;
        c+=edge[i^1].val;
        r=TO;
    }
    return c;
}
void SPFA()
{
    memset(dis,0x7f,sizeof(dis));
    memset(vis,false,sizeof(vis));
    dis[S]=0; Q.push(S); vis[S]=true;
    int x,i;
    while(!Q.empty())
    {
        x=Q.front(); Q.pop(); vis[x]=false;
        for(i=fst[x];~i;i=NXT[i])
        {
            if(!SIZ) continue;
            if(dis[TO]<=dis[x]+VAL) continue;
            dis[TO]=dis[x]+VAL;
            pre[TO]=i^1;
            if(vis[TO]) continue;
            vis[TO]=true;
            Q.push(TO);
        }
    }
    cost+=Augment2();
}
//
int main()
{
    init1();
    bfs();
    ISAP();
    init2();
    for(int i=1;i<=k;i++) SPFA();
    printf("%d\n",cost);
    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

/**************************************************************

Problem: 1834

User: OceanEYe

Language: C++

Result: Accepted

Time:56 ms

Memory:1948 kb

****************************************************************/

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cstdlib>

#include <vector>

#include <queue>

#include <set>

#define p(x) ('0'<=x&&x<='9')

#define INF 100000000

char cc; int C;

template <class T>

void read(T &x)

{

cc=getchar(); C=1; x=0;

while(!p(cc))

{

if(cc=='-') C=-1;

cc=getchar();

}

while(p(cc)) x=x*10+cc-48,cc=getchar();

x*=C;

}

template <class T>

void MN(T &x,T y) { x>y?x=y:x=x; }

using namespace std;

#define N 1005

#define E 10010

struct Tedge

{

int from,to,cap,flow;

int val;

}edge[E<<2];

#define TO edge[i].to

#define VAL edge[i].val

#define SIZ (edge[i].cap-edge[i].flow)

#define CAP edge[i].cap

int fst[N],NXT[E<<2],e_tot;

void add_e(int _,int __,int ___,int ____)

{

edge[e_tot].to=__; edge[e_tot].cap=___; edge[e_tot].from=_; edge[e_tot].val=____;

NXT[e_tot]=fst[_]; fst[_]=e_tot++;

edge[e_tot].to=_; edge[e_tot].cap=___; edge[e_tot].flow=___; edge[e_tot].from=__; edge[e_tot].val=-____;

NXT[e_tot]=fst[__]; fst[__]=e_tot++;

}

int S,T;

struct rec

{

int a,b,c,d;

rec(int _,int __,int ___,int ____): a(_),b(__),c(___),d(____) {}

};

vector <rec> R;

int n,m,k;

void init1()

{

read(n); read(m); read(k);

S=1; T=n;

int _,__,___,____;

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

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

{

read(_); read(__); read(___); read(____);

add_e(_,__,___,0);

R.push_back(rec(_,__,___,____));

}

bool vis[N];

int d[N],cnt[N],p[N],pre[N],ans;

int Augment()

{

int r=T,c=INF,i;

while(r!=S)

{

i=pre[r];

MN(c,CAP-SIZ);

r=TO;

}

r=T;

while(r!=S)

{

i=pre[r];

edge[i].flow-=c; edge[i^1].flow+=c;

r=TO;

}

return c;

}

void ISAP()

{

int node=S,c;

for(int i=1;i<=n;i++) p[i]=fst[i];

bool flag;

while(d[S]<=n)

{

if(node==T)

{

ans+=Augment();

node=S;

}

//solve

flag=false;

for(int i=p[node];~i;i=NXT[i])

{

if(d[TO]!=d[node]-1||SIZ==0) continue;

p[node]=i;

pre[TO]=i^1;

node=TO;

flag=true;

break;

}

if(flag) continue;

c=n+10;

for(int i=fst[node];~i;i=NXT[i])

{

if(!SIZ) continue;

MN(c,d[TO]+1);

}

if(--cnt[d[node]]==0)

{

printf("%d ",ans);

return;

}

cnt[d[node]=c]++;

p[node]=fst[node];

if(node!=S)node=edge[pre[node]].to;

//retreat

}

printf("%d ",ans);

}

queue<int> Q;

void bfs()

{

int x;

memset(vis,0,sizeof(vis));

d[T]=1; Q.push(T); vis[T]^=1;

while(!Q.empty())

{

x=Q.front(); Q.pop();

cnt[d[x]]++;

for(int i=fst[x];~i;i=NXT[i])

{

if(vis[TO]||SIZ) continue;

d[TO]=d[x]+1;

Q.push(TO);

vis[TO]^=1;

}

int dis[N],cost;

void init2()

{

int _,__,___,____;

for(int i=0;i<m;i++)

{

_=R[i].a;

__=R[i].b;

____=R[i].d;

add_e(_,__,INF,____);

}

int Augment2()

{

int r=T,c=0,i;

while(r!=S)

{

i=pre[r];

edge[i].flow--; edge[i^1].flow++;

c+=edge[i^1].val;

r=TO;

}

return c;

}

void SPFA()

{

memset(dis,0x7f,sizeof(dis));

memset(vis,false,sizeof(vis));

dis[S]=0; Q.push(S); vis[S]=true;

int x,i;

while(!Q.empty())

{

x=Q.front(); Q.pop(); vis[x]=false;

for(i=fst[x];~i;i=NXT[i])

{

if(!SIZ) continue;

if(dis[TO]<=dis[x]+VAL) continue;

dis[TO]=dis[x]+VAL;

pre[TO]=i^1;

if(vis[TO]) continue;

vis[TO]=true;

Q.push(TO);

}

cost+=Augment2();

}

int main()

{

init1();

bfs();

ISAP();

init2();

for(int i=1;i<=k;i++) SPFA();

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

return 0;

}

OceanEye's Blog

很多人即使只见过一面，已经算见过了最后一面。

@OceanEye7年前

BZOJ1834

BZOJ1834

撤销评论

近期文章

标签