Selecting Edges SOLUTION SELEDGE

Selecting Edges November Challenge 2020

You are given an undirected graph G with N vertices (numbered 1 through N) and M edges (numbered 1 through M). G does not contain any self-loops, but it may contain parallel edges. For each valid i, the i-th vertex has a non-negative integer weight Ai. Also, for each valid i, the i-th edge has a non-negative integer weight Bi.
Let E={1,2,…,M} denote the set of edges and for any subset S⊆E, let V(S) denote the set of vertices which are endpoints of at least one edge from S. You should find
maxS⊆E,|S|≤K⎛⎝∑v∈V(S)Av−∑e∈SBe⎞⎠.
In other words, among all subsets of at most K (but possibly zero) edges, you should find the largest value of the expression “sum of weights of their endpoints, where each endpoint is counted only once, minus the sum of weights of these edges”. Note that S may contain multiple parallel edges with the same weights ― they are still considered distinct.
Input
The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains three space-separated integers N, M and K.
The second line contains N space-separated integers A1,A2,…,AN.
M lines follow. For each valid i, the i-th of these lines contains three space-separated integers ui, vi and Bi, describing an edge between vertices ui and vi with weight Bi.
Output
For each test case, print a single line containing one integer ― the largest value of the given expression.
Constraints
T=5
1≤N,M≤100
1≤K≤10
0≤Ai≤108 for each valid i
0≤Bi≤108 for each valid i
1≤ui,vi≤N for each valid i
ui≠vi for each valid i
Subtasks
Subtask #1 (5 points):
G does not contain any cycles or parallel edges
K≤7
Subtask #2 (15 points):
Ai=1 for each valid i
Bi=0 for each valid i
K≤7
Subtask #3 (65 points): K≤9
Subtask #4 (15 points): original constraints
Example Input
1
5 5 2
1 2 4 8 16
1 2 1
1 3 2
3 4 2
4 5 2
2 5 1
Example Output
27
Explanation
Example case 1:
The largest value is obtained when S contains only edges (2,5) and (3,4). In that case, V(S) contains the vertices 2,3,4,5.
SOLUTION : credit to : xyr2005
 
#include<bits/stdc++.h>
 
#define lowbit(x) ((x)&(-(x)))
#define DEBUG fprintf(stderr,”Running on Line %d in Function %sn”,__LINE__,__FUNCTION__)
#define SZ(x) ((int)x.size())
#define mkpr std::make_pair
#define pb push_back
 
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef std::pair<int,int> pi;
typedef std::pair<ll,ll> pl;
using std::min;
using std::max;
 
const int inf=0x3f3f3f3f,Inf=0x7fffffff;
const ll INF=0x3f3f3f3f3f3f3f3f;
 
std::mt19937 Rnd(std::chrono::steady_clock::now().time_since_epoch().count());
inline uint rnd(){return Rnd()+Rnd();}
template <typename _Tp>_Tp gcd(const _Tp &a,const _Tp &b){return (!b)?a:gcd(b,a%b);}
template <typename _Tp>inline _Tp abs(const _Tp &a){return a>=0?a:-a;}
template <typename _Tp>inline void chmax(_Tp &a,const _Tp &b){(a<b)&&(a=b);}
template <typename _Tp>inline void chmin(_Tp &a,const _Tp &b){(b<a)&&(a=b);}
template <typename _Tp>inline void read(_Tp &x)
{
char ch(getchar());bool f(false);while(!isdigit(ch)) f|=ch==45,ch=getchar();
x=ch&15,ch=getchar();while(isdigit(ch)) x=(((x<<2)+x)<<1)+(ch&15),ch=getchar();
f&&(x=-x);
}
template <typename _Tp,typename… Args>inline void read(_Tp &t,Args &…args){read(t);read(args…);}
inline int read_str(char *s)
{
char ch(getchar());while(ch==’ ‘||ch==’r’||ch==’n’) ch=getchar();
char *tar=s;*tar=ch,ch=getchar();while(ch!=’ ‘&&ch!=’r’&&ch!=’n’&&ch!=EOF) *(++tar)=ch,ch=getchar();
return tar-s+1;
}
 
const int N=205;
struct edge{
int v,nxt;
int w;
int cost;
}c[N<<3];
int front[N],edge_cnt;
inline void addedge(int u,int v,int w,int cost)
{
c[++edge_cnt]=(edge){v,front[u],w,cost},front[u]=edge_cnt;
c[++edge_cnt]=(edge){u,front[v],0,-cost},front[v]=edge_cnt;
}
int dep[N];
int cur[N],S,T;
bool inq[N];
int _q[N*N],_l,_r;
int node_cnt;
inline void init(){memset(front,255,sizeof(front)),edge_cnt=-1;}
bool bfs()
{
memset(dep,-63,(node_cnt+2)<<2);
memcpy(cur,front,(node_cnt+2)<<2);
memset(inq,0,node_cnt+2);
_q[_l=_r=1]=S,dep[S]=0;
while(_l!=_r+1)
{
int x=_q[_l++];
inq[x]=false;
for(int i=front[x];~i;i=c[i].nxt)
{
int v=c[i].v;
if(c[i].w&&dep[v]<dep[x]+c[i].cost)
{
dep[v]=dep[x]+c[i].cost;
if(!inq[v]) inq[v]=true,_q[++_r]=v;
}
}
}
return dep[T]>=0;
}
int dfs(int x,int flow)
{
if(x==T||!flow) return flow;
inq[x]=true;
int f=0,rf;
for(int &i=cur[x];~i;i=c[i].nxt)
{
if(!inq[c[i].v]&&dep[c[i].v]==dep[x]+c[i].cost&&(rf=dfs(c[i].v,min(flow,c[i].w))))
{
flow-=rf,f+=rf;
c[i].w-=rf,c[i^1].w+=rf;
if(!flow) return f;
}
}
return f;
}
int dinic()
{
int ans=0;
while(bfs()) ans+=dep[T]*dfs(S,inf);
return ans;
}
int a[N],st[N];
std::vector<pi> e[N];
void MAIN()
{
int n,m,k;read(n,m,k);
for(int i=1;i<=n;++i) e[i].clear();
for(int i=1;i<=n;++i) read(a[i]);
int x,y,z;
for(int i=1;i<=m;++i) read(x,y,z),e[x].pb({y,z}),e[y].pb({x,z});
int ans=0;
for(int _=1;_<=4000;++_)
{
init();
int qwq=0;
for(int i=1;i<=n;++i) st[i]=rnd()&1,qwq+=st[i]==0;
S=n+qwq+1,T=S+1,node_cnt=T+1;
int __=T+1;
qwq=0;
for(int i=1;i<=n;++i)
{
if(st[i]==0)
{
++qwq;
addedge(S,i,1,a[i]);
addedge(S,qwq+n,inf,0);
for(auto it:e[i])
{
int v=it.first,w=it.second;
if(st[v]) addedge(i,v,1,-w),addedge(qwq+n,v,1,-w);
}
}
else addedge(i,__,1,a[i]);
}
addedge(__,T,k,0);
chmax(ans,dinic());
}
printf(“%dn”,ans);
}
int main()
{
int _;read(_);
while(_–) MAIN();
return 0;
}

November Challenge 2020 SOLUTION CodeChef

October Lunchtime 2020 CodeChef SOLUTIONS

RELATED :

Related :

Related :

Leave a Comment

close
error: Content is protected !!