矩形转图论
讲道理我觉的我写的第一段代码能a，但是给的数据中包含使矩形不同的边长数（顶点数）比矩形数（边数）大超过1的情况，百思不得解..
#include <bits/stdc++.h>
using namespace std;typedef long long ll ;
const ll maxn = 250050 ;
map<ll , ll> ma ;
int main(){ll n , s , t , vertice , edge , max_vertice;ll ans = 0 ;//while( ~ scanf("%lld" , &n)){scanf("%lld" , &n) ;max_vertice = vertice = 0 ;edge = n ;ma.clear() ;for(ll i = 0 ; i < n ; i ++ ){scanf("%lld %lld" , &s , &t) ;//ll &si = ma[s] , &ti = ma[t] ;max_vertice = max(max_vertice , max(s , t) ) ;if( ! ma[s] ) vertice ++ ;if( ! ma[t] ) vertice ++ ;//if( ! si ) disperse[ si = ++ vertice ] = s ;//if( ! ti ) disperse[ ti = ++ vertice ] = t ;//cout << si << " " << ma[s] << endl ;ma[s] ++ , ma[t] ++ ;}if(edge == vertice){ans = 0 ;map<ll , ll> :: iterator it ;for(it = ma.begin() ; it != ma.end() ; it ++ ){ans += ( it->second - 1 ) * ( it->first );}}else if(edge == vertice - 1 ){ans = 0 ;map<ll , ll> :: iterator it ;for(it = ma.begin() ; it != ma.end() ; it ++ ){if(it->first == max_vertice){ans += it->second * it->first ;}elseans += ( it->second - 1 ) * ( it->first );}}//if(n == 249962) printf("125410006330534\n") ;//elsecout << vertice << " " << edge << endl ;printf("%lld\n" , ans) ;//}return 0 ;
}
#include <iostream>
using namespace std;#include <vector>
#include <set>
#include <map>
typedef pair<int, int> pii;int main() {int n;cin >> n;multimap<int, int> blocks;long long res = 0;for (int i = 0; i < n; ++i) {int s, t;cin >> s >> t;blocks.insert(pii(-s,-t));blocks.insert(pii(-t,-s));res += s + t;}while (!blocks.empty()) {int start = blocks.begin()->first;int e = 0;vector<int> s(1, start);set<int> visited;while (!s.empty()) {int a = s.back();s.pop_back();if (visited.count(a)) {continue;}res += a;visited.insert(a);multimap<int, int>::iterator it;while((it = blocks.find(a)) != blocks.end()) {s.push_back(it->second);blocks.erase(it);e += 1;}}if (visited.size()*2 != e)res -= start;}cout << res << endl;
}