一開始用鄰接矩陣交TLE 分析以後發現 O(n^3) = 1500^3 必須超時
但是對於 鄰接表 O(m*n) = 1500 * 15000 對於兩秒來說完全夠了
所以我把木板推倒重寫了一遍二分圖...還是挺有成就感的...至少以後的題目都可以用把原來低效的木板推掉了
都忘記說題意了...就是給你一棵樹, 求最小的點能覆蓋所有的邊...他們說用什麼樹形DP做我想想貌似也能搞...但這題對於二分圖木板就完全就是裸題了
然後這圖是無向圖,所以最後的結果要/2 這個應該很容易證明了 我就不贅述了
二分圖鄰接表木板如下:
[cpp]
#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;
//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<<hungary()/2<<endl;
}
return 0;
}
#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;
//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<<hungary()/2<<endl;
}
return 0;
}
