一开始用邻接矩阵交TLE 分析以后发现 O(n^3) = 1500^3 必须超时
但是对于 邻接表 O(m*n) = 1500 * 15000 对于两秒来说完全够了
所以我把木板推倒重写了一遍二分图...还是挺有成就感的...至少以后的题目都可以用把原来低效的木板推掉了
都忘记说题意了...就是给你一棵树, 求最小的点能覆盖所有的边...他们说用什么树形DP做我想想貌似也能搞...但这题对于二分图木板就完全就是裸题了
然后这图是无向图,所以最后的结果要/2 这个应该很容易证明了 我就不赘述了
二分图邻接表木板如下
/********************* Template ************************/ #include <set> #include <map> #include <list> #include <cmath> #include <ctime> #include <deque> #include <queue> #include <stack> #include <bitset> #include <cstdio> #include <string> #include <vector> #include <cassert> #include <cstdlib> #include <cstring> #include <sstream> #include <fstream> #include <numeric> #include <iomanip> #include <iostream> #include <algorithm> #include <functional> using namespace std; #define EPS 1e-8 #define MAXN 1550 #define MOD (int)1e9+7 #define PI acos(-1.0) #define DINF (1e10) #define LINF ((1LL)<<50) #define INF (0x3f3f3f3f) #define max(a,b) ((a) > (b) ? (a) : (b)) #define min(a,b) ((a) < (b) ? (a) : (b)) #define max3(a,b,c) (max(max(a,b),c)) #define min3(a,b,c) (min(min(a,b),c)) #define BUG cout<<"BUG! "<<endl #define line cout<<"--------------"<<endl #define L(t) (t << 1) #define R(t) (t << 1 | 1) #define Mid(a,b) ((a + b) >> 1) #define lowbit(a) (a & -a) #define FIN freopen("in.txt","r",stdin) #define FOUT freopen("out.txt","w",stdout) #pragma comment (Linker,"/STACK:102400000,102400000") // typedef long long LL; // typedef unsigned long long ULL; // typedef __int64 LL; // typedef unisigned __int64 ULL; // LL gcd(LL a,LL b){ return b?gcd(b,a%b):a; } // LL lcm(LL a,LL b){ return a*b/gcd(a,b); } /********************* F ************************/ struct Edge{ int u,v,w; // 起点 终点 权值 Edge(int _u = 0,int _v = 0,int _w = 0):u(_u),v(_v),w(_w){}; }; vector<Edge> vec[MAXN]; // 邻接表 int n; // 点的个数 int Link[MAXN]; // Link[v] = u 表示匹配 bool used[MAXN]; // v是否访问 bool dfs(int u){ //从1开始标号 for(int i = 0; i < vec[u].size(); i++){ int v = vec[u][i].v; if(!used[v]){ used[v] = true; if(Link[v] == -1 || dfs(Link[v])){ Link[v] = u; return true; } } } return false; } int hungary(){ int res = 0; memset(Link,-1,sizeof(Link)); for(int u = 1; u <= n; u++){ memset(used,0,sizeof(used)); if(dfs(u)) res++; } return res; } void ini(){ for(int i = 0 ; i < MAXN ; i++) vec[i].clear(); } int main() { while(~scanf("%d",&n)){ ini(); for(int i = 0,a,b,c; i < n; i++){ scanf("%d:(%d)",&a,&b); while(b--){ scanf("%d",&c); vec[a+1].push_back(Edge(a+1,c+1,0)); vec[c+1].push_back(Edge(c+1,a+1,0)); } } cout<<hungary()/2<<endl; } return 0; }
转载于:https://www.cnblogs.com/Felix-F/archive/2013/04/10/3223627.html
