网站 粘度,后台网站模板 html,福州网站建设策划方案,江苏营销型网站推广QWQ嘤嘤嘤 感觉是最水的一道\(G\)题了 顺便记录一下第一次在考场上做出来G qwqqq 题目大意就是说#xff1a; 给你n个点#xff0c;m条边#xff0c;让你选出来一些边#xff0c;最大化边权减点权 \(n\le 1000\) QWQ 看完这个题和数据范围#xff0c;第一感觉就是网络流啊…QWQ嘤嘤嘤 感觉是最水的一道\(G\)题了 顺便记录一下第一次在考场上做出来G qwqqq 题目大意就是说 给你n个点m条边让你选出来一些边最大化边权减点权 \(n\le 1000\) QWQ 看完这个题和数据范围第一感觉就是网络流啊QWQ首先我们可以将一条边视为依赖于两个端点也就是表示你要是选择了这一条边的收益必须付出剩下两个点的代价。 那么这就是一个经典的最大权闭合子图 \(从S向每个边对应的点连边权然后每个边向两个端点连inf然后每个端点向T连点权\) 最后用\(sum边权 - 最小割\)就是最大收益了 #includeiostream
#includecstdio
#includealgorithm
#includecstring
#includecmath
#includequeue
#define int long long
using namespace std;
inline int read()
{int x0,f1;char chgetchar();while (!isdigit(ch)) {if (ch-) f-1;chgetchar();}while (isdigit(ch)) {x(x1)(x3)ch-0;chgetchar();}return x*f;
}
const int maxn 4010;
const int maxm 1e61e2;
const int inf 1e9;
int point[maxn],nxt[maxm],to[maxm],val[maxm];
int h[maxn];
int cnt1;
queueint q;
int s,t;
int n,m;
int ans;
int a[maxn],b[maxn];
void addedge(int x,int y,int w)
{nxt[cnt]point[x];to[cnt]y;val[cnt]w;point[x]cnt;
}
void insert(int x,int y,int w)
{addedge(x,y,w);addedge(y,x,0);
}
bool bfs(int s)
{memset(h,-1,sizeof(h));h[s]0;q.push(s);while (!q.empty()){int x q.front();q.pop();for (int ipoint[x];i;inxt[i]){int p to[i];if (val[i]0 h[p]-1){h[p]h[x]1;q.push(p);}}}if (h[t]-1) return false;else return true;
}
int dfs(int x,int low)
{if (xt || low0) return low;int totflow0;for (int ipoint[x];i;inxt[i]){int p to[i];if (val[i]0 h[p]h[x]1){int tmp dfs(p,min(low,val[i]));low-tmp;totflowtmp;val[i]-tmp;val[i^1]tmp;if (low0) return totflow;}}if (low0) h[x]-1;return totflow;
}
int dinic()
{int ans0;while (bfs(s)){ansansdfs(s,inf);}return ans;
}
int x[maxm],y[maxm],w[maxm];
signed main()
{nread(),mread();for (int i1;in;i) a[i]read();smaxn-10;ts1;for (int i1;im;i){x[i]read(),y[i]read(),w[i]read();insert(s,in,w[i]);insert(in,x[i],inf);insert(in,y[i],inf);ansansw[i];}for (int i1;in;i){insert(i,t,a[i]);}coutans-dinic();return 0;
} 转载于:https://www.cnblogs.com/yimmortal/p/10161890.html
