动态加点跑 EK。

我的代码跑到最后会有负环，不判负环样例都过不去，判负环会小 T 2个点。但是发现题解好像都没有判啊！

感觉也没有写假啊，求助大佬qwq。

#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define maxn 1105
#define put() putchar('\n')
#define Tp template<typename T>
#define Ts template<typename T,typename... Ar>
using namespace std;
Tp void read(T &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
#define fi first
#define se second
#define mk make_pair
const int mod=1e9+7;
const int inf=1e15;
int power(int x,int y=mod-2) {
	int sum=1;
	while (y) {
		if (y&1) sum=sum*x%mod;
		x=x*x%mod;y>>=1;
	}
	return sum;
}
int head=1,h[maxn];
struct yyy {
	int to,z,w,val;
	void add(int x,int y,int W,int V) {
		to=y;z=h[x];h[x]=head;w=W;val=V;
	}
}a[2000005];
int dis[maxn],pre[maxn],fl[maxn];
void ins(int x,int y,int z,int val) {
	// gdb(x,y,z,val);
	a[++head].add(x,y,z,val);
	a[++head].add(y,x,0,-val);
}
int s,t,n,m,sum,ans,tot[maxn],vis[maxn],nex[maxn];
queue<int>q;
bool bfs(void) {
	int i,x;
	memset(tot,0,sizeof(tot));
	memset(dis,0x3f,sizeof(dis));
	fl[s]=inf,dis[s]=0;q.push(s);
	while (!q.empty()) {
		x=q.front();q.pop();++tot[x];vis[x]=0;
		if (tot[x]>t) return gdb(tot[x]),0;//判负环？？？
		// 去掉这行以后样例都跑不出来
		// gdb(x,dis[x],fl[x]);
		for (i=h[x];i;i=a[i].z) if (a[i].w&&dis[a[i].to]>dis[x]+a[i].val) {
			fl[a[i].to]=min(fl[x],a[i].w);
			dis[a[i].to]=dis[x]+a[i].val;
			pre[a[i].to]=i;
			if (!vis[a[i].to]) vis[a[i].to]=1,q.push(a[i].to);
		} 
	}
	if (dis[t]>=inf) return 0;
	int now=t,res=fl[t];
	// gdb(res,dis[t]);
	ans+=res*dis[t];
	while (now^s) {
		a[pre[now]].w-=res,a[pre[now]^1].w+=res;
		nex[a[pre[now]^1].to]=now;
		now=a[pre[now]^1].to;
	}
	return 1;
}
int p[maxn],c[105][105],nums[maxn],id[maxn];
signed main(void){
  //下面是读入和建图
	int i,j;
	read(n);read(m);
	for (i=1;i<=n;i++) read(p[i]),sum+=p[i];
	for (i=1;i<=n;i++) for (j=1;j<=m;j++) read(c[j][i]);
	int cnt=n+m;s=0;t=n+m*2+sum;
	for (i=1;i<=n;i++) ins(m+i,t,p[i],0);
	for (i=1;i<=m;i++) ins(s,i,inf,0);
	for (i=1;i<=m;i++) {
		++cnt;++nums[i];
		ins(i,cnt,1,0);
		for (j=1;j<=n;j++) {
			ins(cnt,j+m,1,c[i][j]*nums[i]);
		}
	}
	int times=0;
	while (bfs()) {
		int now=t;
		i=nex[s];
		// ins(s,i,1,0);
		++cnt;++nums[i];
		ins(i,cnt,1,0);
		for (j=1;j<=n;j++) 
			ins(cnt,j+m,1,c[i][j]*nums[i]);
	}
	printf("%lld\n",ans);
	return 0;
}
//i=begin && g++ $i.cpp -o $i -std=c++14 -O2 && ./$i