两个等价代码,为什么一个TLE一个AC?
查看原帖
两个等价代码,为什么一个TLE一个AC?
151425
千年知乎_天才楼主2023/9/22 16:56

不是常数问题,下了数据,一个马上过一个根本跑不出来。

//TLE
#include<bits/stdc++.h>
#define au arc[u]
using namespace std;
const int N = 5e3 + 5, M = 1e5 + 5;
const int INF = 0x3f3f3f3f;
int s,t,n, m,u,v, tot = 1, last[N], arc[N], to[M], back[M], w[M], c[M], dist[N], cg;
bool in[N];
queue<int>q;
void link(int u,int v,int weight,int cost){
	to[++tot]=v,w[tot]=weight,c[tot]=cost;
	back[tot]=last[u],last[u]=tot;
}
bool spfa(){
	memcpy(arc,last,sizeof last),
	memset(dist,0x3f,sizeof dist);
	for(q.push(s),in[s]=true,dist[s]=0;!q.empty();q.pop(),in[u]=false){
		for(int i=last[u=q.front()];i;i=back[i]){
			if(w[i]&&dist[v=to[i]]>dist[u]+c[i]){
				dist[v]=dist[u]+c[i];
				if(!in[v])q.push(v),in[v]=true;
			}
		}
	}
	return dist[t]!=1061109567;
}

int dfs(int u,int maxi) {
  if (u == t) return maxi;
  int sum=0,flow;in[u]=true;
  for (; arc[u]; arc[u] = back[arc[u]]) {
    v = to[arc[u]];
    if (!in[v]  && dist[v] == dist[u] + c[arc[u]]) {
      flow= dfs(v,std::min(w[arc[u]], maxi - sum));
      cg += flow* c[arc[u]], w[arc[u]] -= flow, w[arc[u] ^ 1] += flow, sum += flow;
      if(sum>=maxi)break;
    }
  }
  in[u]=false;
  return sum;
}
int main() {
	int w,c;
  for(scanf("%d%d%d%d",&n,&m,&s,&t);m--;)
    scanf("%d%d%d%d", &u, &v, &w, &c),
    link(u, v, w, c),link(v,u,0,-c);
  int ans = 0;
  while (spfa()) 
    for(int flow;(flow = dfs(s, INF));) ans += flow;
  printf("%d %d\n", ans, cg);
  return 0;
}
//AC
#include<bits/stdc++.h>
#define au arc[u]
using namespace std;
const int N = 5e3 + 5, M = 1e5 + 5;
const int INF = 0x3f3f3f3f;
int s,t,n, m,u,v, tot = 1, last[N], arc[N], to[M], back[M], w[M], c[M], dist[N], cg;
bool in[N];
queue<int>q;
void link(int u,int v,int weight,int cost){
	to[++tot]=v,w[tot]=weight,c[tot]=cost;
	back[tot]=last[u],last[u]=tot;
}
bool spfa(){
	memcpy(arc,last,sizeof last),
	memset(dist,0x3f,sizeof dist);
	for(q.push(s),in[s]=true,dist[s]=0;!q.empty();q.pop(),in[u]=false){
		for(int i=last[u=q.front()];i;i=back[i]){
			if(w[i]&&dist[v=to[i]]>dist[u]+c[i]){
				dist[v]=dist[u]+c[i];
				if(!in[v])q.push(v),in[v]=true;
			}
		}
	}
	return dist[t]!=1061109567;
}

int dfs(int u,int maxi) {
  if (u == t) return maxi;
  int sum=0,flow;in[u]=true;
  for (; arc[u]&&sum<maxi; arc[u] = back[arc[u]]) {
    v = to[arc[u]];
    if (!in[v]  && dist[v] == dist[u] + c[arc[u]]) {
      flow= dfs(v,std::min(w[arc[u]], maxi - sum));
      cg += flow* c[arc[u]], w[arc[u]] -= flow, w[arc[u] ^ 1] += flow, sum += flow;
    }
  }
  in[u]=false;
  return sum;
}
int main() {
	int w,c;
  for(scanf("%d%d%d%d",&n,&m,&s,&t);m--;)
    scanf("%d%d%d%d", &u, &v, &w, &c),
    link(u, v, w, c),link(v,u,0,-c);
  int ans = 0;
  while (spfa()) 
    for(int flow;(flow = dfs(s, INF));) ans += flow;
  printf("%d %d\n", ans, cg);
  return 0;
}

唯一区别就是dinic()把判断跳出的语句放出来了,不信的文件对比。

2023/9/22 16:56
加载中...