泉州网站建设网站,wordpress相关文章插件,制作网页的收获,网上国网app官方下载Minimum grid
题意#xff1a;
一个n * n的矩阵#xff0c;有m个位置需要填数#xff0c;填的数的范围是0k1e6,需要满足第i行的最大值是b#xff0c;第j列的最大值是ci#xff0c;求一个满足条件的最小代价 n2e3,m8e5,k1e6
题解#xff1a;
如果…Minimum grid
题意
一个n * n的矩阵有m个位置需要填数填的数的范围是0k1e6,需要满足第i行的最大值是b第j列的最大值是ci求一个满足条件的最小代价 n2e3,m8e5,k1e6
题解
如果直接填我们需要满足每行每列的最大值第i行最大值是a第j行最大值是b我们需要第i行单独有一个格子权值是a第j行单独有一个格子的权值是b这样代价是ab但是如果第i行和第j行的最大值都是a我们可以直接在(i,j)这个格子上放a这样即满足条件且代价降低(用一个a干了两个a的事) 如果现在第1行第2行第3行第3列第4列的最大值都是a那么才怎么分配呢我们把行放一侧列放一侧这不就是二分图吗跑最大匹配即可,最大匹配就省下的a的数量。也就是当前值对应的行数当前值对应的列数-最大匹配值 * 当前值 当然前提是这几个位置都允许填 我们可以直接枚举最大值K跑多次二分图然后计算每次贡献得到答案 不过每种权值互相不影响可以建立多个二分图一次跑完
代码
#includebits/stdc.h
#define debug(a,b) printf(%s %d\n,a,b);
typedef long long ll;
using namespace std;
//Fe~Jozky
const ll INF_ll1e18;
const int INF_int0x3f3f3f3f;
inline ll read(){ll s0,w1ll;char chgetchar();while(ch0||ch9){if(ch-)w-1ll;chgetchar();}while(ch0ch9) ss*10ll((ch-0)*1ll),chgetchar();//s(s3)(s1)(ch^48);return s*w;
}
const int maxn3e39;
int a[maxn],b[maxn];
vectorintg[maxn];
int match[maxn];
bool vis[maxn];
ll ans;
int n,m,k;
bool dfs(int x){for(int v:g[x]){if(vis[v])continue;vis[v]1;if(!match[v]||dfs(match[v])){match[v]x;return 1;}}return 0;
}
int main()
{cinnmk;for(int i1;in;i)cina[i];for(int j1;jn;j)cinb[j];while(m--){int x,y;cinxy;if(a[x]b[y])//如果该行最大值等于列最大值 g[x].push_back(y);}for(int i1;in;i){memset(vis,0,sizeof(vis));dfs(i);}for(int i1;in;i)//没有优化的结果 ansa[i]b[i];for(int i1;in;i)if(match[i])ans-b[i];//可以省掉b[i] coutans;
}