请加强数据
查看原帖
请加强数据
681351
Tobiichi_Origami楼主2023/10/10 20:52
#include<bits/stdc++.h>
using namespace std;
const int N=210,M=1e5+10,K=110;
const int Inf=0x3f3f3f3f;
struct edge{
    int to,next,w;
    double cost;
}ed[M<<1];
int he[N],tot=-1;
double dis[N],p[K][K];
int cur[N],a[K],b[K];
bool is[K][K],vis[N];
int n,m,s,t;
void insert(int u,int v,int w,double c){
    tot++;
    ed[tot].to=v;
    ed[tot].w=w;
    ed[tot].cost=c;
    ed[tot].next=he[u];
    he[u]=tot;
}
bool spfa(){
    for(int i=s;i<=t;i++) dis[i]=-Inf;
	memset(vis,0,sizeof(vis));
	queue<int>q;
	dis[s]=0;vis[s]=1;
	q.push(s);cur[s]=he[s];
	while(!q.empty()){
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=he[u];i!=-1;i=ed[i].next){
			int v=ed[i].to;
			if(dis[v]<dis[u]+ed[i].cost&&ed[i].w){
				dis[v]=dis[u]+ed[i].cost;
				cur[v]=he[v];
				if(!vis[v]){
					vis[v]=1;
					q.push(v);
				}
			}
		}
	}
	return dis[t]!=-Inf;
}
int dfs(int u,int lim){
	if(u==t) return lim;
	vis[u]=1;
	int flow=0;
	for(int i=cur[u];i!=-1&&flow<lim;i=ed[i].next){
		int v=ed[i].to;
		cur[u]=i;
		if(dis[v]==dis[u]+ed[i].cost&&ed[i].w&&!vis[v]){
			int t=dfs(v,min(ed[i].w,lim-flow));
			if(!t) continue;
			ed[i].w-=t,ed[i^1].w+=t;
			flow+=t;
		}
	}
    vis[u]=0;
	return flow;
}
int dinic(){
	int res=0,flow;
	while(spfa())
		while(flow=dfs(s,Inf))
			res+=flow;
	return res;
}
int main()
{
    memset(he,-1,sizeof(he));
    scanf("%d %d",&n,&m);
    s=0,t=n+m+1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%lf",p[i][j]);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=m;i++)
        scanf("%d",&b[i]);
    for(int i=1;i<=n;i++)
        insert(s,i,a[i],0),insert(i,s,0,0);
    for(int i=1;i<=m;i++)
        insert(i+n,t,b[i],0),insert(t,i+n,0,0);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            insert(i,j+n,1,p[i][j]*0.01);
            insert(j+n,i,0,-p[i][j]*0.01);
        }
    dinic();
    for(int u=1;u<=n;u++)
        for(int i=he[u];i!=-1;i=ed[i].next)
            if(!ed[i].w) is[u][ed[i].to-n]=1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)
            printf("%d",is[i][j]);
        puts("");
    }
    return 0;
}

此代码漏洞百出,却拿到了最优解,求加强数据

2023/10/10 20:52
加载中...