hdu1827Summer Holiday(强连通分量-最小权点基)

xiaoxiao2021-02-28  16

Summer Holiday

Time Limit: 10000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 4111    Accepted Submission(s): 1853 Problem Description To see a World in a Grain of Sand  And a Heaven in a Wild Flower,  Hold Infinity in the palm of your hand  And Eternity in an hour.                    —— William Blake 听说lcy帮大家预定了新马泰7日游,Wiskey真是高兴的夜不能寐啊,他想着得快点把这消息告诉大家,虽然他手上有所有人的联系方式,但是一个一个联系过去实在太耗时间和电话费了。他知道其他人也有一些别人的联系方式,这样他可以通知其他人,再让其他人帮忙通知一下别人。你能帮Wiskey计算出至少要通知多少人,至少得花多少电话费就能让所有人都被通知到吗?   Input 多组测试数组,以EOF结束。 第一行两个整数N和M(1<=N<=1000, 1<=M<=2000),表示人数和联系对数。 接下一行有N个整数,表示Wiskey联系第i个人的电话费用。 接着有M行,每行有两个整数X,Y,表示X能联系到Y,但是不表示Y也能联系X。   Output 输出最小联系人数和最小花费。 每个CASE输出答案一行。   Sample Input 12 16 2 2 2 2 2 2 2 2 2 2 2 2 1 3 3 2 2 1 3 4 2 4 3 5 5 4 4 6 6 4 7 4 7 12 7 8 8 7 8 9 10 9 11 10   Sample Output 3 6   Author 威士忌   Source HDOJ 2007 Summer Exercise(3)- Hold by Wiskey   Recommend 威士忌   |   We have carefully selected several similar problems for you:   1823  1824  1826  1822  1825  思路:最小权点基模板题,首先求出所有的强连通分量,把所有分量缩成一个点,于是该图变成了有向无环图,接下来找出所有强连通分量的最小权点,如果该连通分量入度为0,直接加上此连通分量的最小权点的权值。注意该题输入数据量较大,不能使用c++的输入流,否则会超时。。。 代码: #include<iostream> #include<algorithm> #include<cstring> #include<vector> #include<stack> #include<cstdio> #include<climits> using namespace std; #define inf INT_MAX const int mx = 1010; int dfn[mx],low[mx],vis[mx],num[mx],dg[mx],pay[mx],mi[mx]; int n,m,id,cnt,ans; vector<int> mp[mx]; stack<int> s; void init(){ cnt=0; id=0; ans=0; memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low)); memset(vis,0,sizeof(vis)); memset(num,0,sizeof(num)); memset(dg,0,sizeof(dg)); memset(mi,0,sizeof(mi)); for(int i=1;i<=n;i++) mp[i].clear(); while(!s.empty()) s.pop(); } void tarjan(int x){ dfn[x]=low[x]=++id; s.push(x); vis[x]=1; for(int i=0;i<mp[x].size();i++){ int t=mp[x][i]; if(!dfn[t]) { tarjan(t); low[x]=min(low[x],low[t]); }else if(vis[t]) low[x]=min(low[x],dfn[t]); } if(dfn[x]==low[x]){ int tp,tt=inf; cnt++; do{ tp=s.top(); vis[tp]=0; num[tp]=cnt; if(pay[tp]<tt) tt=pay[tp]; ///tt=min(tt,pay[tp]); s.pop(); }while(tp!=x); mi[cnt]=tt; } } void solve(){ int sum=0; for(int i=1;i<=n;i++) for(int j=0;j<mp[i].size();j++) if(num[i]!=num[mp[i][j]]) dg[num[mp[i][j]]]++; for(int i=1;i<=cnt;i++){ if(!dg[i]) { sum++; ans+=mi[i]; } } printf("%d %d\n",sum,ans); ///cout<<sum<<" "<<ans<<endl; } int main(){ while(~scanf("%d%d",&n,&m)){ init(); for(int i=1;i<=n;i++) scanf("%d",&pay[i]); for(int i=0;i<m;i++){ int a,b; ///cin>>a>>b;果断超时 scanf("%d%d",&a,&b); mp[a].push_back(b); } for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i); solve(); } }
转载请注明原文地址: https://www.6miu.com/read-1650228.html

最新回复(0)