徐汇制作网站哪家好,邵阳建网站多少钱,免费微网站系统,版面设计的概念题意
在一个图中 给出了每个点得权值和连边 想要尽可能删除一些联通的点数小于2的点 删完后 求最后剩下联通块内点得数量是奇数的权值和
分析
本题由于在删除点得过程中需要考虑 当把当前点删除后 其联通的点也有可能会因为当前点得删除而连边小于2同时删除 考虑拓扑排序 建…题意
在一个图中 给出了每个点得权值和连边 想要尽可能删除一些联通的点数小于2的点 删完后 求最后剩下联通块内点得数量是奇数的权值和
分析
本题由于在删除点得过程中需要考虑 当把当前点删除后 其联通的点也有可能会因为当前点得删除而连边小于2同时删除 考虑拓扑排序 建立邻接表和每个点得联通数目表将每个小于2的点入队 然后拓扑处理 对当前点 将其连边的点联通数目– 若小于2入队 继续处理直到队空后 dfs算一下奇数联通快就得到结果了 注意初始化和下标操作别搞错了
CODE
#includebits/stdc.h
using namespace std;
typedef long long ll;
const int maxn 10010;
vectorintv[maxn];
int k,a[maxn],cnt[maxn];;
bool ifn[maxn];
ll ss;
ll dfs(int s){for(int i0;iv[s].size();i){if(!ifn[v[s][i]]){k;ifn[v[s][i]]1;ssa[v[s][i]];dfs(v[s][i]);}}
}
int main()
{int t;scanf(%d,t);while(t--){int n,m;scanf(%d%d,n,m);ll sum0;for(int i1;in;i)scanf(%d,a[i]);while(m--){int s,e;scanf(%d%d,s,e);v[s].push_back(e);//记录连边v[e].push_back(s);cnt[e],cnt[s];//记录连接的点得数量}queueintq;while(!q.empty())q.pop();for(int i1;in;i)if(cnt[i]2)q.push(i),ifn[i]1;//将连点小于2的点入队 删去while(!q.empty()){int p q.front();q.pop();for(int i0;iv[p].size();i){//将删去的点连接的点的连接数--cnt[v[p][i]]--;if(!ifn[v[p][i]]cnt[v[p][i]]2)q.push(v[p][i]),ifn[v[p][i]]1;//如果这个点的连点数小于2并且未被删去 则入队并删除标记}}for(int i1;in;i){if(!ifn[i]){ifn[i]1;k1;ssa[i];dfs(i);if(k%21)sumss;}}printf(%lld\n,sum);memset(cnt1,0,sizeof(int)*n);for(int i1;in;i)v[i].clear();memset(ifn1,0,sizeof(bool)*n);}return 0;
}
