wap浏览器手机版,seo优化培训学校,wordpress发不了文章,价格低的自动挡汽车正题
题目链接:https://www.luogu.com.cn/problem/P4716 题目大意
给出nnn个点mmm条边的一张有向图#xff0c;求以rrr为根的最小外向树。 1≤n≤100,1≤m≤1041\leq n\leq 100,1\leq m\leq 10^41≤n≤100,1≤m≤104 解题思路
考虑一种贪心#xff0c;对于每个点我们先选出…正题
题目链接:https://www.luogu.com.cn/problem/P4716 题目大意
给出nnn个点mmm条边的一张有向图求以rrr为根的最小外向树。
1≤n≤100,1≤m≤1041\leq n\leq 100,1\leq m\leq 10^41≤n≤100,1≤m≤104 解题思路
考虑一种贪心对于每个点我们先选出一个连入的最小的边权但是这样可能产生环。
考虑暴力将环去掉我们枚举所有的环然后将环缩成一个点之后然后每个环外的边都减去入点所连接边的权值可撤销贪心。
然后问题规模就缩小了不断重复上述过程即可。
时间复杂度O(n(nm))O(n(nm))O(n(nm)) code
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N110;
struct node{int x,y,w;
}e[N*N];
int n,m,r,h[N],pre[N],v[N],id[N],ans;
int main()
{scanf(%d%d%d,n,m,r);for(int i1;im;i)scanf(%d%d%d,e[i].x,e[i].y,e[i].w);while(1){memset(h,0x3f,sizeof(h));memset(v,0,sizeof(v));memset(id,0,sizeof(id));for(int i1;im;i)if(e[i].x!e[i].ye[i].wh[e[i].y])h[e[i].y]e[i].w,pre[e[i].y]e[i].x;for(int i1;in;i)if(i!rh[i]h[0])return puts(-1)0;int cnt0;for(int p1;pn;p){if(pr)continue;int xp;ansh[x];while(x!rv[x]!p!id[x])v[x]p,xpre[x];if(x!r!id[x]){id[x]cnt;for(int ypre[x];y!x;ypre[y])id[y]cnt;}}if(cnt0)break;for(int i1;in;i)if(!id[i])id[i]cnt;for(int i1;im;i){e[i].w-h[e[i].y];e[i].xid[e[i].x];e[i].yid[e[i].y];}rid[r];ncnt;}printf(%d\n,ans);return 0;
}
