rt,本地使用MSVS运行正常,g++不论是本地还是在线都不行,代码如下
#include<bits/stdc++.h>
using namespace std;
namespace IO
{
bool EOFstate = 0;
template<typename T>inline void read(T &x)
{
x = 0; int f = 1; char c = getchar();
while(('0' > c || c > '9') && !EOFstate) { if(c == '-')f = -1; c = getchar(), EOFstate = c == EOF; }
while('0' <= c && c <= '9')x = (x << 3) + (x << 1) + c - '0', c = getchar();
x *= f;
}
template<typename T = int>inline T read()
{
T x;
x = 0; int f = 1; char c = getchar();
while(('0' > c || c > '9') && !EOFstate) { if(c == '-')f = -1; c = getchar(), EOFstate = c == EOF; }
while('0' <= c && c <= '9')x = (x << 3) + (x << 1) + c - '0', c = getchar();
x *= f;
return x;
}
template<typename T>inline void write(T x, char end = ' ')
{
if(x == 0)return putchar('0'), putchar(end), void();
if(x < 0)putchar('-'), x = -x;
char c[21], cnt = 0;
while(x)c[cnt++] = x % 10 + '0', x /= 10;
while(cnt)putchar(c[--cnt]); putchar(end);
}
}using namespace IO;
//const int Nn=10,Mm=20,P=80,N=Mm*P,M=100,inf=0x3f3f3f3f;
const int Nn=100,Mm=200,P=800,N=Mm*P,M=10000000,inf=0x3f3f3f3f;
int head[N],to[M],nxt[M],cap[M],val[M],tot=1;
int n,m,S,T,SUM;
int cost[Nn][Mm];
inline void _add(int f,int t,int c,int v)
{
to[++tot]=t,nxt[tot]=head[f],head[f]=tot,cap[tot]=c,val[tot]=v;
}
inline void add(int f,int t,int c,int v,int ic=0)
{
_add(f,t,c,v),_add(t,f,ic,-v);
}
inline int getid(int k,int x)
{
return (k-1)*m+x;
}
inline pair<int,int>invid(int x)
{
return {(x-1)/m+1,(x-1)%m+1};
}
inline void addcook(int k,int x)
{
int id=getid(k,x);
for(int i=1;i<=n;++i)
{
add(SUM+i,id,1,k*cost[i][x]);
}
add(id,T,1,0);
}
int dis[N],cur[N];
bitset<N>vis;
inline bool spfa()
{
memset(dis,0x3f,sizeof(dis));
queue<int>q;
dis[S]=0,q.push(S),vis[S]=1;
while(q.size())
{
int p=q.front();q.pop();vis[p]=0;
for(int i=head[p];i;i=nxt[i])
{
if(cap[i]&&dis[to[i]]>dis[p]+val[i])
{
dis[to[i]]=dis[p]+val[i];
//cout<<tot<<' ';
if(!vis[to[i]])
q.push(to[i]),vis[to[i]]=1;
}
}
}
return (dis[T]!=0x3f3f3f3f);
}
vector<int> from;
int sumcost;
int dfs(int p,int mx,int f)
{
if(p==T)
return from.push_back(f),mx;
vis[p]=1;
int tmx=mx;
for(int &i=cur[p],c;i&&tmx;i=nxt[i])
{
if(cap[i]&&!vis[to[i]]&&dis[to[i]]==dis[p]+val[i])
{
c=dfs(to[i],min(cap[i],tmx),p);
cap[i]-=c,cap[i^1]+=c,tmx-=c;
sumcost+=c*val[i];
}
}
vis[p]=0;
return mx-tmx;
}
inline int dinic()
{
int ans=0;
bool f;
while(f=spfa())
{
memcpy(cur,head,sizeof(cur));
ans+=dfs(S,inf,0);
for(auto i:from)
{
auto t=invid(i);
addcook(t.first+1,t.second);
}
from.clear();
//printf("%d %d\n",tot,ans);
}
}
int main()
{
read(n),read(m);
SUM=m*P,T=SUM+n+1;
for(int i=1,t;i<=n;++i)
{
read(t);
add(S,SUM+i,t,0);
}
for(int i=1;i<=n;++i)
{
for(int j=1;j<=m;++j)
read(cost[i][j]);
}
for(int i=1;i<=m;++i)
addcook(1,i);
dinic();
write(sumcost);
return 0;
}