关于 #3 TLE
查看原帖
关于 #3 TLE
121813
老子是北瓜楼主2022/1/27 16:38

我感觉我的思路和题解是一样的,可是为什么会T在#3呢??

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
#include<queue>
#define N 50
#define M 80050
#define inf (1<<25)
using namespace std;

int n,m,p[N],a[105][N],tot=1,t,sum,mincost;
int d[M],pre[M],h[M];
bool vis[M];
vector<int> g[M];
queue<int> q;
struct edge{
	int to,w,c;
} e[10000005];

int qread(){
	int num=0; char ch=getchar();
	while(ch<'0' || ch>'9') ch=getchar();
	while(ch>='0' && ch<='9') {
		num=num*10+ch-'0';
		ch=getchar();
	}
	return num;
}
void addedge(int x,int y,int w,int c){
	e[++tot].to=y; e[tot].w=w; e[tot].c=c; g[x].push_back(tot);
	e[++tot].to=x; e[tot].w=0; e[tot].c=-c; g[y].push_back(tot);
}

bool spfa(){
	memset(d,0x3f,sizeof(d));
	d[0]=0; q.push(0);
	
	while(!q.empty())
	{
		int u=q.front(); q.pop(); vis[u]=0;
		for(int i=0; i<g[u].size(); ++i)
		{
			int tag=g[u][i],v=e[tag].to,w=e[tag].w,c=e[tag].c;
			if(!w || d[v] <= d[u]+c) continue;
			d[v] = d[u]+c;
			pre[v] = tag;
			if(!vis[v])
			{
				vis[v]=1;
				q.push(v);
			}
		}
	}
	return d[t] < 1000000000;
}

// num = (times-1)*m+i
void update()
{
	int point=t;
	mincost+=d[t];
	while(point)
	{
		point=pre[point];
		--e[point].w;
		++e[point^1].w;
		point=e[point^1].to;
		if(1 <= point && point <= sum*m)
		{
			int op=point%m,k=(point-1)/m+1;
			if(op==0) op=m;
			if(h[op]==k){
				++h[op];
				for(int i=1; i<=n; ++i)
					addedge(k*m+op,sum*m+i,1,(k+1)*a[op][i]);
				addedge(0,k*m+op,1,0);
			}
		}
	}
}

int main(){
	n=qread(); m=qread();
	for(int i=1; i<=n; ++i){
		p[i]=qread();
		sum+=p[i];
	}
	t=sum*m+n+1;
	for(int i=1; i<=n; ++i){
		addedge(sum*m+i,t,p[i],0);
		for(int j=1; j<=m; ++j)
			a[j][i]=qread();
	}
	
	for(int i=1; i<=m; ++i){
		h[i]=1;
		for(int j=1; j<=n; ++j)
			addedge(i,sum*m+j,1,a[i][j]);
		addedge(0,i,1,0);
	}
	
	while(spfa()) update();
	
	printf("%d",mincost);
	return 0;
}
2022/1/27 16:38
加载中...