codeforce链接
昨天看到这道图论题感觉挺有意思的，记录下来。
代码：
#include<iostream> #include<algorithm> #include<cstdio> #include<vector> #include<stack> #include<cstring> #include<map> #include<queue> #include<cmath> #include<set> #include<deque> #define INF 0x3f3f3f3f #define lowbit(a) ((a)&-(a)) #define speed std::ios::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL) using namespace std; typedef long long ll; queue<ll> q; stack<ll> s; deque<ll> deq; priority_queue<ll> pq; const ll maxn = 2005; ll n,m,l,r,num; ll ans=0; ll a[maxn],x[maxn],y[maxn],tmp[maxn],c[maxn],k[maxn],res[maxn]; ll read() { int x=0; int k=1; char c=getchar(); while(c>'9'||c<'0') { if(c=='-') k=-1; c=getchar(); } while(c>='0'&&c<='9') x=x*10+c-'0', c=getchar(); return x*k; } ll pre[maxn]; bool vis[maxn],build[maxn]; void init() { for(ll i=1;i<=n;i++) pre[i]=i; } void find() //优先建发电厂 { ll minn=INF; ll pos; for(ll i=1;i<=n;i++){ //先找一个未搜寻的最小的建发电厂 if(!vis[i]&&minn>tmp[i]) minn=tmp[i],pos=i; } if(tmp[pos]==c[pos]) //如果没有被建桥 build[pos]=true,++num; vis[pos]=true; //表示已被建发电厂或已建桥 ans+=tmp[pos]; //建发电厂开支或建桥开支 for(ll i=1;i<=n;i++){ //与每一个点比较是建桥比较省还是建发电厂省 if(!vis[i]&&tmp[i]>(abs(x[i]-x[pos])+abs(y[i]-y[pos]))*(k[i]+k[pos]))//与当前的点相连看哪个更省 tmp[i]=(abs(x[i]-x[pos])+abs(y[i]-y[pos]))*(k[i]+k[pos]), pre[i]=pos; //建桥比较省的把他们连起来 } } int main() { cin>>n; init(); for(ll i=1;i<=n;i++){ cin>>x[i]>>y[i]; } for(ll i=1;i<=n;i++){ cin>>c[i]; tmp[i]=c[i]; //初始化本身建发电厂的费用 } for(ll i=1;i<=n;i++){ cin>>k[i]; } for(ll i=1;i<=n;i++){//每个点都来一次 find(); } cout<<ans<<"\n"<<num<<"\n"; for(ll i=1;i<=n;i++){ if(build[i]) cout<<i<<" "; } cout<<"\n"<<n-num<<"\n"; for(ll i=1;i<=n;i++){ if(pre[i]!=i) cout<<i<<" "<<pre[i]<<"\n"; } } `