不开O2能过,开了结果全T了
查看原帖
不开O2能过,开了结果全T了
237893
donkeys楼主2022/5/15 14:22

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;
}
2022/5/15 14:22
加载中...