[COGS 741]负载平衡
这个网络流题挺简单的……
首先从[tex]S[/tex]向每个点连容量为该点存货量的边（费用为0）。首先注意最后所有存货量都要变成总的平均值，所以要从每个点向[tex]T[/tex]连一条容量为总的平均值的边（费用为0）。最后根据题目要求在相邻点之间连边（容量都是无限大，费用为1）。
跑一遍最小费用最大流，得出的费用就是答案。
代码：
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn=110;
namespace MCMF{
struct Edge{
int u,v,cap,flow,cost;
};
vector<Edge> edges;
vector<int> G[maxn];
int m;
inline void AddEdge(int u,int v,int cap,int cost){
edges.push_back((Edge){u,v,cap,0,cost});
edges.push_back((Edge){v,u,0,0,-cost});
m=edges.size();
G[u].push_back(m-2);
G[v].push_back(m-1);
}
int a[maxn];
bool inQueue[maxn];
int d[maxn],p[maxn];
bool BellmanFord(int s,int t,long long& cost){
register int i,u;
queue<int> Q;
memset(d,0x7f,sizeof(d));
memset(inQueue,0,sizeof(inQueue));
d[s]=0;
inQueue[s]=true;
p[s]=0;
a[s]=0x7f7f7f7f;
Q.push(s);
while(!Q.empty()){
u=Q.front();
Q.pop();
inQueue[u]=false;
for(i=0;i<G[u].size();i++){
Edge& e=edges[G[u][i]];
if(e.cap>e.flow && d[e.v]>d[u]+e.cost){
d[e.v]=d[u]+e.cost;
p[e.v]=G[u][i];
a[e.v]=min(a[u],e.cap-e.flow);
if(!inQueue[e.v]){
Q.push(e.v);
inQueue[e.v]=true;
}
}
}
}
if(d[t]==0x7f7f7f7f)
return false;
cost+=((long long)d[t])*((long long)a[t]);
for(u=t;u!=s;u=edges[p[u]].u){
edges[p[u]].flow+=a[t];
edges[p[u]^1].flow-=a[t];
}
return true;
}
long long MincostMaxflow(int s,int t){
register long long ans=0;
while(BellmanFord(s,t,ans));
return ans;
}
};
int A[maxn];
int main(){
register int i,ave=0;
int n;
freopen("overload.in","r",stdin);
freopen("overload.out","w+",stdout);
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%d",&A[i]);
ave+=A[i];
MCMF::AddEdge(0,i,A[i],0);
}
ave/=n;
for(i=1;i<=n;i++){
MCMF::AddEdge(i,n+1,ave,0);
if(i>1){
MCMF::AddEdge(i-1,i,0x7f7f7f7f,1);
MCMF::AddEdge(i,i-1,0x7f7f7f7f,1);
}
if(i<n){
MCMF::AddEdge(i+1,i,0x7f7f7f7f,1);
MCMF::AddEdge(i,i+1,0x7f7f7f7f,1);
}
}
MCMF::AddEdge(1,n,0x7f7f7f7f,1);
MCMF::AddEdge(n,1,0x7f7f7f7f,1);
printf("%lld\n",MCMF::MincostMaxflow(0,n+1));
fclose(stdin);
fclose(stdout);
return 0;
}
[COGS 727]太空飞行计划
第一次做最大权闭合图……so sad
关于最大权闭合图的做法，可以参考胡伯涛前辈的《最小割模型在信息学竞赛中的应用》。不过很麻烦的事是……打印方案。
注意，割走的边要么和[tex]S[/tex]相连，要么就和[tex]T[/tex]相连。如果一条从[tex]S[/tex]到[tex]E_i[/tex]被割走了，那么就说明[tex]E_i[/tex]没有被选择；如果一条从[tex]I_i[/tex]到[tex]T[/tex]的边被割走了，那么就说明[tex]I_i[/tex]被选择了。
于是乎，Dinic最后一次造层次图的时候（这次最终将不能到达[tex]T[/tex]），如果某个点（除了[tex]S[/tex]和[tex]T[/tex]）被访问到了，那个点就被选择了。
最小割的结果是所有拒绝的实验的能赚的钱及所有选用的仪器消耗的钱的和。也就是说，答案就是[tex]p[/tex]的和减去最小割。
代码：
#include <cstdio>
#include <iostream>
#include <iterator>
#include <cstring>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <algorithm>
#include <bitset>
using namespace std;
const int maxn=211;
const int INF=0x7fffffff;
#define REP(i,n) for(i=0;i<(n);i++)
#define REP_B(i,n) for(i=1;i<=(n);i++)
#define CL_ARR(x,v) memset(x,v,sizeof(x))
struct Edge{
int u,v,cap,flow;
};
namespace Dinic{
vector<Edge> edges;
vector<int> G[maxn];
int m;
inline void AddEdge(int u,int v,int cap){
edges.push_back((Edge){u,v,cap,0});
edges.push_back((Edge){v,u,0,0});
m=edges.size();
G[u].push_back(m-2);
G[v].push_back(m-1);
}
bool vis[maxn];
int d[maxn],cur[maxn];
int s,t;
inline bool BFS(){
register int i,u;
queue<int> Q;
CL_ARR(vis,0);
Q.push(s);
d[s]=0;
vis[s]=true;
while(!Q.empty()){
u=Q.front();
Q.pop();
REP(i,G[u].size()){
Edge& e=edges[G[u][i]];
if(!vis[e.v] && e.cap>e.flow){
vis[e.v]=1;
d[e.v]=d[u]+1;
Q.push(e.v);
}
}
}
return vis[t];
}
int DFS(int x,int a){
if(x==t || a==0)
return a;
int flow=0,temp;
for(int& i=cur[x];i<G[x].size();i++){
Edge& e=edges[G[x][i]];
if(d[e.v]==d[x]+1){
temp=DFS(e.v,min(a,e.cap-e.flow));
if(temp>0){
e.flow+=temp;
edges[G[x][i]^1].flow-=temp;
flow+=temp;
a-=temp;
if(a==0)
break;
}
}
}
return flow;
}
inline int Mincut(int S,int T){
s=S;
t=T;
register int ans=0;
while(BFS()){
CL_ARR(cur,0);
ans+=DFS(s,INF);
}
return ans;
}
};
vector<int> AnsList;
int main(){
register int i,j,ans=0;
int m,n,p,x;
bool flag;
string line;
// ios::sync_with_stdio(false);
// cin.tie(0);
freopen("shuttle.in","r",stdin);
freopen("shuttle.out","w+",stdout);
ostream_iterator<int> output(cout," ");
scanf("%d %d\n",&m,&n);
REP_B(i,m){
getline(cin,line);
stringstream ss(line);
ss>>p;
ans+=p;
Dinic::AddEdge(0,i,p);
while(ss>>x){
Dinic::AddEdge(i,m+x,INF);
}
}
REP_B(i,n){
cin>>p;
Dinic::AddEdge(i+m,n+m+1,p);
}
ans-=Dinic::Mincut(0,n+m+1);
REP_B(i,m){
if(Dinic::vis[i]){
AnsList.push_back(i);
}
}
copy(AnsList.begin(),AnsList.end(),output);
cout<<endl;
AnsList.clear();
REP_B(i,n){
if(Dinic::vis[i+m]){
AnsList.push_back(i);
}
}
copy(AnsList.begin(),AnsList.end(),output);
cout<<endl;
cout<<ans<<endl;
return 0;
}
[COGS 732]试题库
这个题和那个圆桌聚餐很像。
不过注意一点，一个题如果有多种类型，那么那个题最后只能归结到一种题型中。有些同学可能就因此怀疑样例（尽管有SPJ）。
所以最后的建图就是这样：从[tex]S[/tex]向所有题目结点连一条容量为1的边，每个题目向对应题型连一条容量为1的边，每个题型向[tex]T[/tex]连一条容量为该类型题目需要数量的边。跑一遍最大流即可，当且仅当最大流为[tex]m[/tex]时有解。
输出解吧其实也不难，直接判断从题目结点出发的弧是否满载即可。注意不要把反向弧和普通弧弄混。
代码：
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int maxn=1030,maxk=25;
#define REP(i,n) for(i=0;i<(n);i++)
#define REP_B(i,n) for(i=1;i<=(n);i++)
#define CL_ARR(x,v) memset(x,v,sizeof(x))
struct Edge{
int u,v,cap,flow;
};
namespace Dinic{
vector<Edge> edges;
vector<int> G[maxn];
int m;
inline void AddEdge(int u,int v,int cap){
edges.push_back((Edge){u,v,cap,0});
edges.push_back((Edge){v,u,0,0});
m=edges.size();
G[u].push_back(m-2);
G[v].push_back(m-1);
}
bool vis[maxn];
int d[maxn],cur[maxn];
int s,t;
inline bool BFS(){
register int i,u;
queue<int> Q;
CL_ARR(vis,0);
Q.push(s);
d[s]=0;
vis[s]=true;
while(!Q.empty()){
u=Q.front();
Q.pop();
REP(i,G[u].size()){
Edge& e=edges[G[u][i]];
if(!vis[e.v] && e.cap>e.flow){
vis[e.v]=1;
d[e.v]=d[u]+1;
Q.push(e.v);
}
}
}
return vis[t];
}
int DFS(int x,int a){
if(x==t || a==0)
return a;
int flow=0,temp;
for(int& i=cur[x];i<G[x].size();i++){
Edge& e=edges[G[x][i]];
if(d[e.v]==d[x]+1){
temp=DFS(e.v,min(a,e.cap-e.flow));
if(temp>0){
e.flow+=temp;
edges[G[x][i]^1].flow-=temp;
flow+=temp;
a-=temp;
if(a==0)
break;
}
}
}
return flow;
}
inline int Maxflow(int S,int T){
s=S;
t=T;
register int ans=0;
while(BFS()){
CL_ARR(cur,0);
ans+=DFS(s,0x7f7f7f7f);
}
return ans;
}
};
vector<int> ans[maxn];
int main(){
int k,n,u,p;
register int i,j,m=0,flow;
freopen("testlib.in","r",stdin);
freopen("testlib.out","w+",stdout);
scanf("%d%d",&k,&n);
REP_B(i,k){
scanf("%d",&u);
m+=u;
Dinic::AddEdge(i+n,k+n+1,u);
}
REP_B(i,n){
scanf("%d",&p);
Dinic::AddEdge(0,i,1);
REP_B(j,p){
scanf("%d",&u);
Dinic::AddEdge(i,n+u,1);
}
}
flow=Dinic::Maxflow(0,n+k+1);
if(flow!=m){
puts("NoSolution!");
return 0;
}
REP_B(i,n){
for(j=0;j<Dinic::G[i].size();j++){
Edge& e=Dinic::edges[Dinic::G[i][j]];
if(e.v>n && e.v<=(n+k) && e.cap==e.flow){
ans[e.v-n].push_back(i);
}
}
}
REP_B(i,k){
printf("%d:",i);
REP(j,ans[i].size()){
printf(" %d",ans[i][j]);
}
putchar('\n');
}
return 0;
}
[COGS 740]分配问题
很明显是二分图最大权匹配。可以用匈牙利算法求解，但我比较弱……所以就写了个费用流。
注意最优解和最差解都要给出！
代码：
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int maxn=205;
namespace MCMF{
struct Edge{
int u,v,cap,flow,cost;
};
vector<Edge> edges;
vector<int> G[maxn];
int m;
inline void AddEdge(int u,int v,int cap,int cost){
edges.push_back((Edge){u,v,cap,0,cost});
edges.push_back((Edge){v,u,0,0,-cost});
m=edges.size();
G[u].push_back(m-2);
G[v].push_back(m-1);
}
inline void ClearGraph(){
register int i;
edges.clear();
for(i=0;i<maxn;i++)
G[i].clear();
}
int a[maxn];
bool inQueue[maxn];
int d[maxn],p[maxn];
bool BellmanFord(int s,int t,long long& cost){
register int i,u;
queue<int> Q;
memset(d,0x7f,sizeof(d));
memset(inQueue,0,sizeof(inQueue));
d[s]=0;
inQueue[s]=true;
p[s]=0;
a[s]=0x7f7f7f7f;
Q.push(s);
while(!Q.empty()){
u=Q.front();
Q.pop();
inQueue[u]=false;
for(i=0;i<G[u].size();i++){
Edge& e=edges[G[u][i]];
if(e.cap>e.flow && d[e.v]>d[u]+e.cost){
d[e.v]=d[u]+e.cost;
p[e.v]=G[u][i];
a[e.v]=min(a[u],e.cap-e.flow);
if(!inQueue[e.v]){
Q.push(e.v);
inQueue[e.v]=true;
}
}
}
}
if(d[t]==0x7f7f7f7f)
return false;
cost+=((long long)d[t])*((long long)a[t]);
for(u=t;u!=s;u=edges[p[u]].u){
edges[p[u]].flow+=a[t];
edges[p[u]^1].flow-=a[t];
}
return true;
}
long long MincostMaxflow(int s,int t){
register long long ans=0;
while(BellmanFord(s,t,ans));
return ans;
}
};
int A[105][105];
int main(){
int n;
register int i,j;
freopen("job.in","r",stdin);
freopen("job.out","w+",stdout);
scanf("%d",&n);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++){
scanf("%d",&A[i][j]);
MCMF::AddEdge(i,j+n,1,A[i][j]);
}
for(i=1;i<=n;i++)
MCMF::AddEdge(0,i,1,0);
for(i=n+1;i<=2*n;i++)
MCMF::AddEdge(i,2*n+1,1,0);
printf("%lld\n",MCMF::MincostMaxflow(0,2*n+1));
MCMF::ClearGraph();
for(i=1;i<=n;i++)
for(j=1;j<=n;j++){
MCMF::AddEdge(i,j+n,1,-A[i][j]);
}
for(i=1;i<=n;i++)
MCMF::AddEdge(0,i,1,0);
for(i=n+1;i<=2*n;i++)
MCMF::AddEdge(i,2*n+1,1,0);
printf("%lld\n",-(MCMF::MincostMaxflow(0,2*n+1)));
return 0;
}
[COGS 396]魔术球问题（简化版）
这简化的真彻底……变成一个贪心水体了……
枚举柱子数，然后每次尽可能放球，放不了球了增加柱子，增加不了了就是最优解：
代码：
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
const int maxn=61;
vector<int> V[maxn];
inline bool isSqr(int x){
register int temp=floor(sqrt(x));
return temp*temp==x;
}
int main(){
int n,temp;
bool flag;
register int i,j,ans=1;
freopen("balla.in","r",stdin);
freopen("balla.out","w+",stdout);
scanf("%d",&n);
for(i=1;i<=n;i++){
while(true){
flag=false;
for(j=0;j<i;j++){
if(V[j].empty() || isSqr(V[j].back()+ans)){
V[j].push_back(ans++);
flag=true;
break;
}
}
if(!flag)
break;
}
}
printf("%d\n",ans-1);
return 0;
}
[COGS 729]圆桌聚餐
第一次做这种”大型“网络流题（抱歉我是炒鸡大局若）。
注意同一个单位的人不可同桌聚餐，说明同一单位的人最多只能往某一桌子派一人！然后建图就很简单了：源点往每个单位连流量为[tex]r_i[/tex]的边，每个单位分别向每一个桌连一条流量为1的边，每个桌向汇点连一条流量为[tex]c_i[/tex]的边。跑一遍网络流即可。
这题坑点在于要输出解。输出解的时候注意不要把反向弧和正常的弧搞混。
代码：
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int maxn=425;
#define REP(i,n) for(i=0;i<(n);i++)
#define REP_B(i,n) for(i=1;i<=(n);i++)
#define CL_ARR(x,v) memset(x,v,sizeof(x))
struct Edge{
int u,v,cap,flow;
};
namespace Dinic{
vector<Edge> edges;
vector<int> G[maxn];
int m;
inline void AddEdge(int u,int v,int cap){
edges.push_back((Edge){u,v,cap,0});
edges.push_back((Edge){v,u,0,0});
m=edges.size();
G[u].push_back(m-2);
G[v].push_back(m-1);
}
bool vis[maxn];
int d[maxn],cur[maxn];
int s,t;
inline bool BFS(){
register int i,u;
queue<int> Q;
CL_ARR(vis,0);
Q.push(s);
d[s]=0;
vis[s]=true;
while(!Q.empty()){
u=Q.front();
Q.pop();
REP(i,G[u].size()){
Edge& e=edges[G[u][i]];
if(!vis[e.v] && e.cap>e.flow){
vis[e.v]=1;
d[e.v]=d[u]+1;
Q.push(e.v);
}
}
}
return vis[t];
}
int DFS(int x,int a){
if(x==t || a==0)
return a;
int flow=0,temp;
for(int& i=cur[x];i<G[x].size();i++){
Edge& e=edges[G[x][i]];
if(d[e.v]==d[x]+1){
temp=DFS(e.v,min(a,e.cap-e.flow));
if(temp>0){
e.flow+=temp;
edges[G[x][i]^1].flow-=temp;
flow+=temp;
a-=temp;
if(a==0)
break;
}
}
}
return flow;
}
inline int Maxflow(int S,int T){
s=S;
t=T;
register int ans=0;
while(BFS()){
CL_ARR(cur,0);
ans+=DFS(s,0x7f7f7f7f);
}
return ans;
}
};
int main(){
int n,m,temp;
bool flag;
register int i,j,tag,end,Expect=0;
freopen("roundtable.in","r",stdin);
freopen("roundtable.out","w+",stdout);
scanf("%d%d",&n,&m);
end=n+m+1;
REP_B(i,n){
scanf("%d",&temp);
Expect+=temp;
Dinic::AddEdge(0,i,temp);
}
REP_B(i,m){
scanf("%d",&temp);
tag=i+n;
Dinic::AddEdge(tag,end,temp);
REP_B(j,n){
Dinic::AddEdge(j,tag,1);
}
}
temp=Dinic::Maxflow(0,end);
if(temp<Expect){
puts("0");
return 0;
}
puts("1");
REP_B(i,n){
vector<int> V;
REP(j,Dinic::G[i].size()){
Edge& e=Dinic::edges[Dinic::G[i][j]];
if(e.v>n && e.v<=m+n && e.cap==e.flow)
V.push_back(e.v);
}
sort(V.begin(),V.end());
flag=false;
REP(j,V.size()){
if(flag)
putchar(' ');
flag=true;
printf("%d",V[j]-n);
}
putchar('\n');
}
return 0;
}
