因为本人不会在codeforces上面把代码换行神马的，所以在这里加个链接，一般是错误的代码，目前还没有发表什么文章，所以大家请跳过这篇文章。
【ｐｕｚｚｌｅｓ】
题型：网络流
错误类型：
Runtime Error
(ACCESS_VIOLATION)
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define inf (1<<29)
const int maxn = 33333 , maxm = 60002000;
int NV,n,m;
int gap[maxn],dis[maxn],cur[maxn],pre[maxn];
struct Edge 
{
int v,w,f,next;
Edge() {}
Edge(int _v,int _w,int _next) : v(_v),w(_w),f(0),next(_next){}
}edge[maxm];
int E,head[maxn];
void Init() {
E=0;memset(head,-1,sizeof(int)*NV);
}
void addedge(int u,int v,int w) {
edge[E]=Edge(v,w,head[u]);
head[u]=E++;
edge[E]=Edge(u,w,head[v]);
head[v]=E++;
}
int Sap(int st,int en) {
int maxf = 0;
for(int i=0;i<NV;i++) {
dis[i] = gap[i] = 0;
cur[i] = head[i];
}
int u = pre[st] = st;
int aug = inf;
gap[0] = NV;
while( dis[st] < NV ) {
loop: for(int &i=cur[u];i!=-1;i=edge[i].next) {
int v = edge[i].v;
if(edge[i].f && dis[u] == dis[v] + 1) {
aug = aug<edge[i].f ? aug : edge[i].f;
pre[v] = u;
u = v;
if(v == en) {
maxf += aug;
for(u=pre[u];v!=st;v=u,u=pre[u]) {
edge[cur[u]].f -= aug;
edge[cur[u]^1].f += aug;
}
aug = inf;
}
goto loop;
}
}
int mindis = inf;
for(int i=head[u];i!=-1;i=edge[i].next) {
int v = edge[i].v;
if(edge[i].f && mindis > dis[v]) {
cur[u] = i;
mindis = dis[v];
}
}
if(--gap[dis[u]] == 0) break;
gap[ dis[u] = mindis + 1 ] ++;
u = pre[u];
}
return maxf;
}
int dist[maxn];
int sta[maxn];
bool vis[maxn];
void spfa1(int st,int en) {
int u,v;
for(int i=0;i<NV;i++) {
dist[i]=inf;
pre[i] = -1;
vis[i] = 0;
}
int top = 0;
sta[++top] = st;
dist[st] = 0;
while(top) {
u = sta[top--];
vis[u] = 0;
for(int i=head[u];i!=-1;i=edge[i].next) {
v = edge[i].v;
int w = edge[i].w;
if(dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
if(!vis[v]) {
vis[v] = 1;
sta[++top] = v;
}
}
}
}
}
int rdist[maxn];
void spfa2(int st,int en) {
int u,v;
for(int i=0;i<NV;i++) {
rdist[i]=inf;
pre[i] = -1;
vis[i] = 0;
}
int top = 0;
sta[++top] = st;
rdist[st] = 0;
while(top) {
u = sta[top--];
vis[u] = 0;
for(int i=head[u];i!=-1;i=edge[i].next) {
v = edge[i].v;
int w = edge[i].w;
if(rdist[v] > rdist[u] + w) {
rdist[v] = rdist[u] + w;
if(!vis[v]) {
vis[v] = 1;
sta[++top] = v;
}
}
}
}
}
int main() {
int T;
scanf("%d",&T);
while(T--) {
scanf("%d%d",&n,&m);
NV = n;
Init();
int u,v,w,f;
for(int i=0;i<m;i++) {
scanf("%d%d%d",&u,&v,&w);
u--;v--;
addedge(u,v,w);
}
int st,en;
scanf("%d%d",&st,&en);
st--;en--;
spfa1(st,en);
spfa2(en,st);
//printf("dist of en is %d\n",dist[en]);
//printf("rdist of st is %d\n",rdist[st]);
//for(int i=0;i<n;i++)
// printf("dist of no.%d is %d\n",i+1,dist[i]);
//for(int i=0;i<n;i++)
// printf("rdist od no.%d is %d\n",i+1,rdist[i]);
int mindistance = dist[en];
for(u=0;u<n;u++) {
if(dist[u]+rdist[u] == mindistance) {
for(int i=head[u];i!=-1;i=edge[i].next) {
v=edge[i].v;
if(abs(dist[u]-dist[v]) == edge[i].w)
edge[i].f = 1;
}
}
}
int ans = Sap(st,en);
printf("%d\n",ans);
}
return 0;
}
然后将栈改成了队列仍然是TLE了
I translate the stack to the queue but till TLE , below is the code:
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define inf (1<<29)
const int maxn = 2222 , maxm = 44444;
int n , N , m;
int maxf , minc;
int dist[maxn],p[maxn];
int que[maxn];
bool vis[maxn];
struct Edge {
int u,v,f,c,next;
}edge[maxm];
int E,head[maxn];
void init() {
E=0; memset(head,-1,sizeof(int)*n);
}
void _add(int u,int v,int f,int c) {
edge[E].u=u;edge[E].v=v;edge[E].f=f;edge[E].c=c;edge[E].next=head[u];head[u]=E++;
}
void addedge(int u,int v,int f,int c) {
_add(u,v,f,c); _add(v,u,0,-c);
}
bool spfa(int s,int t) {
for(int i=0;i<n;i++) dist[i]=inf,p[i]=-1,vis[i]=0;
dist[s]=0;
int front = 0 , rear = 0;
que[rear++]=s;
int u,v,f,c;
while(front!=rear) {
u=que[front++];
if(front==maxn) front=0;
for(int i=head[u];i!=-1;i=edge[i].next) {
v=edge[i].v;
f=edge[i].f;
c=edge[i].c;
if(f && dist[v] > dist[u] + c) {
dist[v] = dist[u] + c;
p[v] = i;
if(!vis[v]) {
vis[v] = 1;
que[rear++] = v;
if(rear==maxn) rear = 0;
}
}
}
}
return dist[t] != inf;
}
void mcmf(int s,int t) {
maxf = minc = 0;
while( spfa(s,t) ) {
int minf = inf;
for(int i=p[t];i!=-1;i=p[ edge[i].u ])
if(minf > edge[i].f)
minf = edge[i].f;
maxf += minf;
minc += dist[t] * minf;
for(int i=p[t];i!=-1;i=p[ edge[i].u ]) {
edge[i].f -= minf;
edge[i^1].f += minf;
}
}
return;
}
int main() {
int T,cas=1;
scanf("%d",&T);
while(T--) {
scanf("%d%d",&N,&m);
int s = 0 , t = 2*N + 1;
n = 2*N + 2;
init();
int u,v,c;
while(m--) {
scanf("%d%d%d",&u,&v,&c);
addedge(u,v+N,1,c);
addedge(v,u+N,1,c);
}
for(int i=1;i<=N;i++) {
addedge(s,i,1,0);
addedge(i+N,t,1,0);
}
mcmf(s,t);
printf("Case %d: ",cas++);
if(maxf != N) printf("NO\n");
else printf("%d\n",minc);
}
return 0;
}
posted on 2012-10-07 15:11
YouAreInMyHeart 阅读(282)
评论(0) 编辑 收藏 引用