网站建设中 显示,网站制作流程 优帮云,焦作网站建设哪家专业,live wordpress主题problem 给定一个n*m的网格#xff0c;每条边上有一个权值给定每个机器人的出发位置和目标位置求权值最大solution 拆边#xff0c;每条边拆成2条#xff0c;第一条容量1#xff0c;费用c[i]#xff0c;第二条容量inf,费用0#xff1b;建超级源汇#xff08;s到每个出发… problem 给定一个n*m的网格每条边上有一个权值给定每个机器人的出发位置和目标位置求权值最大solution 拆边每条边拆成2条第一条容量1费用c[i]第二条容量inf,费用0建超级源汇s到每个出发位置容量1费用0每个目标位置到t容量1费用0跑最大费用最大流即可最后输入有点毒。。。 codes #includeiostream
#includealgorithm
#includequeue
#includecstring
using namespace std;const int N 1100, M 100010, inf 130;//Grape
int tot1, head[N], Next[M], ver[M], cap[M], cost[M];
void AddEdge(int x, int y, int z, int c){//正向边初始容量z单位费用cver[tot] y, cap[tot] z, cost[tot] c;Next[tot] head[x], head[x] tot;//反向边初始容量0单位费用-c与正向边成对存储ver[tot] x, cap[tot] 0, cost[tot] -c;Next[tot] head[y], head[y] tot;
}
//Cost flow
int s, t, incf[N], pre[N];
int dist[N], vis[N];
bool spfa(){queueintq;memset(dist,0xcf,sizeof(dist));//-infmemset(vis,0,sizeof(vis));q.push(s); dist[s]0; vis[s]1;incf[s] 130; //到s为止的增广路上各边的最小的剩余容量while(q.size()){int x q.front(); q.pop(); vis[x] 0;for(int i head[x]; i; i Next[i]){if(!cap[i])continue; //剩余容量为0不再残量网络中不遍历int y ver[i];if(dist[y]dist[x]cost[i]){//流量都为1不用乘dist[y] dist[x]cost[i];incf[y] min(incf[x], cap[i]);pre[y] i;//记录前驱用于找方案if(!vis[y])vis[y]1, q.push(y);}}}if(dist[t] 0xcfcfcfcf)return false;//汇点不可达已求出最大流return true;
}
int MaxCostMaxflow(){int flow 0, cost 0;while(spfa()){int x t;while(x ! s){int i pre[x];cap[i] - incf[t];cap[i^1] incf[t];//成对存储x ver[i^1];}flow incf[t];cost dist[t]*incf[t];}return cost;
}//Timu
int a, b, n, m, mp[N][N];
void input(){cinab;cinnm;s 0, t (n1)*(m1)1;int cnt 0;for(int i 0; i n; i)for(int j 0; j m; j)mp[i][j] cnt;for(int i 0; i n; i){for(int j 0; j m; j){int x; cinx;AddEdge(mp[i][j],mp[i][j1],1,x);AddEdge(mp[i][j],mp[i][j1],inf,0);}}for(int j 0; j m; j){for(int i 0; i n; i){int x; cinx;AddEdge(mp[i][j],mp[i1][j],1,x);AddEdge(mp[i][j],mp[i1][j],inf,0);}}for(int i 0; i a; i){int x, y, z; cinzxy;AddEdge(s,mp[x][y],z,0);}for(int i 0; i b; i){int x, y, z; cinzxy;AddEdge(mp[x][y],t,z,0);}return ;
}int main(){ios::sync_with_stdio(false);input();coutMaxCostMaxflow()\n;return 0;
} 转载于:https://www.cnblogs.com/gwj1314/p/9444651.html
