POJ 1463 Strategic game 二分图最小点覆盖 - c++编程基础

一开始用邻接矩阵交TLE 分析以后发现 O(n^3) = 1500^3 必须超时

但是对于邻接表 O(m*n) = 1500 * 15000 对于两秒来说完全够了

所以我把木板推倒重写了一遍二分图...还是挺有成就感的...至少以后的题目都可以用把原来低效的木板推掉了

都忘记说题意了...就是给你一棵树, 求最小的点能覆盖所有的边...他们说用什么树形DP做我想想貌似也能搞...但这题对于二分图木板就完全就是裸题了

然后这图是无向图,所以最后的结果要/2 这个应该很容易证明了我就不赘述了

二分图邻接表木板如下:

[cpp]
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
//typedef long long LL;
//typedef __int64 LL;
//typedef long double DB;
//typedef unisigned __int64 LL;
//typedef unsigned long long ULL;
#define EPS 1e-8
#define MAXN 1600
#define MAXE 300000
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
//#define MOD 99991
//#define MOD 99990001
//#define MOD 1000000007
#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 mabs(a) ((a<0) (-a):a)
//#define L(t) (t << 1) //Left son t*2
//#define R(t) (t << 1 | 1) //Right son t*2+1
//#define Mid(a,b) ((a+b)>>1) //Get Mid
//#define lowbit(a) (a&-a) //Get Lowbit
//int gcd(int a,int b){return b gcd(b,a%b):a;}
//int lcm(int a,int b){return a*b/gcd(a,b);}
struct Edge
{
int u,v,w; // 起点终点权值
int next;
}edge[MAXE];
int head[MAXN]; // 每个点临接的边
int cnt ; // 边的条数
int n ; // 点的个数
int linker[MAXN]; // linker[v] = u 表示匹配
bool used[MAXN]; // 是否访问
void add(Edge x)
{
edge[cnt].u = x.u;
edge[cnt].v = x.v;
edge[cnt].w = x.w;
edge[cnt].next = head[x.u];
head[x.u] = cnt++;
edge[cnt].v = x.u;
edge[cnt].u = x.v;
edge[cnt].w = x.w;
edge[cnt].next = head[x.v];
head[x.v] = cnt++;
}
bool dfs(int u)
{
for(int i = head[u]; i != -1; i = edge[i].next)
{
int v = edge[i].v;
if(!used[v])
{
used[v] = true;
if(linker[v] == -1 || dfs(linker[v]))
{
linker[v] = u;
return true;
}
}
}
return false;
}
int hungary()
{
int res = 0;
memset(linker,-1,sizeof(linker));
for(int u = 0; u < n; u++)
{
memset(used,0,sizeof(used));
if(dfs(u))
res++;
}
return res;
}
int main()
{
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
while(scanf("%d",&n) != EOF)
{
memset(edge,0,sizeof(edge));
memset(head,-1,sizeof(head));
Edge tmp;
cnt = 0;
for(int i = 0; i < n; i++)
{
int a,b,c;
scanf("%d:(%d)",&a,&b);
while(b--)
{
scanf("%d",&c);
tmp.u = a;
tmp.v = c;
add(tmp);
}
}
cout< }
return 0;
}

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
//typedef long long LL;
//typedef __int64 LL;
//typedef long double DB;
//typedef unisigned __int64 LL;
//typedef unsigned long long ULL;
#define EPS 1e-8
#define MAXN 1600
#define MAXE 300000
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
//#define MOD 99991
//#define MOD 99990001
//#define MOD 1000000007
#define max(a,b) ((a)>(b) (a):(b))
#def

POJ 1463 Strategic game 二分图最小点覆盖 (一)