本文主要是介绍bzoj3280(莫名tle)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
已知tle的原因是spfa的死循环，但是为什么死循环呢？
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<queue>
using namespace std;
const int inf=0x7f7f7f7f;
inline int read()
{int ans,f=1;char ch;while ((ch=getchar())<'0'||ch>'9') if (ch=='-') f=-1;ans=ch-'0';while ((ch=getchar())>='0'&&ch<='9') ans=ans*10+ch-'0';return ans*f;
}int n,m,k,s,t,ans;
int id[105][2],total;
int head[105],tot,now[105],pre[105],dis[105];
struct aa
{int to,pre,cap,flow,w;
}edge[100005];
void addedge(int x,int y,int z,int w)
{edge[++tot].to=y;edge[tot].cap=z;edge[tot].w=w;edge[tot].pre=head[x];head[x]=tot;edge[++tot].to=x;edge[tot].cap=0;edge[tot].w=-w;edge[tot].pre=head[y];head[y]=tot;
}
bool b[105];
bool spfa()
{memset(dis,inf,sizeof(dis));memset(b,false,sizeof(b));memset(pre,0,sizeof(pre));memset(now,0,sizeof(now));dis[s]=0;queue<int> q;q.push(s);while (!q.empty()){int u=q.front();q.pop();b[u]=false;for (int i=head[u];i;i=edge[i].pre)if (edge[i].cap>edge[i].flow&&dis[edge[i].to]>dis[u]+edge[i].w){dis[edge[i].to]=dis[u]+edge[i].w;pre[edge[i].to]=u;now[edge[i].to]=i;if (!b[edge[i].to]) {b[edge[i].to]=true;q.push(edge[i].to);}}}if (dis[t]!=inf) return true;return false;
}
int doing()
{int ansf=0;while (spfa()){int flow=inf;for (int i=t;i!=s;i=pre[i])flow=min(flow,edge[now[i]].cap-edge[now[i]].flow);ansf+=flow;ans+=flow*dis[t];for (int i=t;i!=s;i=pre[i]) edge[now[i]].flow+=flow,edge[((now[i]-1)^1)+1].flow-=flow;} return ansf;
}void work()
{memset(head,0,sizeof(head));tot=0;n=read(),m=read(),k=read();int x,y,num=0;s=0,t=n*2+1;for (int i=1;i<=n;i++){x=read();num+=x;addedge(i,t,x,0);addedge(s,n+i,x,0);} for (int i=1;i<=m;i++){x=read(),y=read();addedge(0,1,x,y);}for (int i=1;i<=k;i++){x=read(),y=read();for (int j=1;j<=n;j++)if (j+x+1<=n) addedge(j+n,j+x+1,inf,y);}for (int i=1;i<n;i++) addedge(i,i+1,inf,0);ans=0;printf("Case %d: ",++total);if (doing()!=num) printf("impossible\n");else printf("%d\n",ans);
}int main()
{int T=read();for(int i=1;i<=T;i++) work();return 0;
}
这篇关于bzoj3280(莫名tle)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
